Advanced search
Start date

Graph partitioning problems

Grant number: 15/11930-4
Support Opportunities:Scholarships abroad - Research Internship - Doctorate
Effective date (Start): September 01, 2015
Effective date (End): August 31, 2016
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Yoshiko Wakabayashi
Grantee:Phablo Fernando Soares Moura
Supervisor: Stephan Thomasse
Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
Research place: École Normale Supérieure, Lyon (ENS), France  
Associated to the scholarship:13/19179-0 - Optimization problems on graph partitioning, BP.DR


The focus of this research proposal is the study of partition problems on graphs.We are particularly interested in the proper orientation, path cover, and convex recoloring problems. In the first problem, we have to orient every edge in a graph so that the indegrees of the vertices in this orientation induce a partition of the set of vertices into a minimum number of stable sets.In the second problem, we are interested in finding a partition of the set of vertices of a graph into a minimum number of paths. Finally, in the convex recoloring problem, we have to partition the set of vertices in such a way that each element of this partition induces a connected subgraph of the input graph. (AU)

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

Scientific publications
(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)
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)
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)
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)

Please report errors in scientific publications list by writing to: