Advanced search
Start date
Betweenand

Optimization problems on graph partitioning

Grant number: 13/19179-0
Support type: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 researcher:Yoshiko Wakabayashi
Grantee:Phablo Fernando Soares Moura
Home 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

Abstract

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
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

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)
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 JUL 19 2019. Web of Science Citations: 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, NOV 2017. Web of Science Citations: 1.
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, AUG 2016. Web of Science Citations: 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, MAR 2016. Web of Science Citations: 2.
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 São Paulo.

Please report errors in scientific publications list by writing to: cdi@fapesp.br.