Advanced search
Start date

Optimization problems on graph partitioning

Grant number: 13/19179-0
Support Opportunities:Scholarships in Brazil - Doctorate
Effective date (Start): December 01, 2013
Effective date (End): March 31, 2017
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Yoshiko Wakabayashi
Grantee:Phablo Fernando Soares Moura
Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
Associated scholarship(s):15/11930-4 - Graph partitioning problems, BE.EP.DR


This is the Ph.D. project of Phablo Fernando Soares Moura, to be developed under supervision of Y. Wakabayashi at Instituto de Matemática e Estatística - Universidade de São Paulo.This project falls within the area of combinatorial optimization, and focuses on partitioning problems on graphs under some constraints. One of the problems that will be investigated in this project is the convex recoloring problem. Roughly speaking, the input of this problem is a graph in which the vertices are (arbitrarily) colored, and the objective is minimize the number of color changes so that, for each color in the recoloring, the vertices with this color induce a connected subgraph. Basically, the objective of the recoloring is to partition the vertex set in such a way that each class of the partition induces a connected subgraph.This problem has its origins in the study of phylogenetic trees, but it can be easily extended to more general versions and arbitrary graphs, having been studied under several approaches. It is an NP-hard problem even on paths.We propose to investigate more general versions of this problem on arbitrary graphs, with focus on the study of different integer linear formulations, the relation between such formulations and algorithmic aspects.

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items

Scientific publications (4)
(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)
COELHO, RAFAEL S.; MOURA, PHABLO F. S.; WAKABAYASHI, YOSHIKO. The k-hop connected dominating set problem: approximation and hardness. JOURNAL OF COMBINATORIAL OPTIMIZATION, v. 34, n. 4, p. 1060-1083, . (13/03447-6, 15/11930-4, 13/19179-0)
ABOULKER, PIERRE; COHEN, NATHANN; HAVET, FREDERIC; LOCHET, WILLIAM; MOURA, PHABLO F. S.; THOMASSE, STEPHAN. Subdivisions in digraphs of large out-degree or large dichromatic number. ELECTRONIC JOURNAL OF COMBINATORICS, v. 26, n. 3, . (15/11930-4, 16/21250-3, 17/22611-2, 13/19179-0)
CAMPELO, MANOEL; MOURA, PHABLO F. S.; SANTOS, MARCIO C.. Lifted, projected and subgraph-induced inequalities for the representatives k-fold coloring polytope. DISCRETE OPTIMIZATION, v. 21, p. 131-156, . (13/03447-6, 15/11930-4, 13/19179-0)
CAMPELO, MANOEL; FREIRE, ALEXANDRE S.; LIMA, KARLA R.; MOURA, PHABLO F. S.; WAKABAYASHI, YOSHIKO. The convex recoloring problem: polyhedra, facets and computational experiments. MATHEMATICAL PROGRAMMING, v. 156, n. 1-2, p. 303-330, . (13/03447-6, 13/19179-0, 12/17585-9)
Academic Publications
(References retrieved automatically from State of São Paulo Research Institutions)
MOURA, Phablo Fernando Soares. Graph colorings and digraph subdivisions. 2017. Doctoral Thesis - Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) São Paulo.

Please report errors in scientific publications list using this form.