Scholarship 15/11930-4 - Grafos, Teoria dos grafos - BV FAPESP
Advanced search
Start date
Betweenand
Related content

Graph partitioning problems

Grant number: 15/11930-4
Support Opportunities:Scholarships abroad - Research Internship - Doctorate
Start date until: September 01, 2015
End date until: 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
Institution abroad: École Normale Supérieure, Lyon (ENS), France  
Associated to the scholarship:13/19179-0 - Optimization problems on graph partitioning, BP.DR

Abstract

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:
More itemsLess items
Articles published in other media outlets ( ):
More itemsLess items
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

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)
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)
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 using this form.