Scholarship 16/21250-3 - Algoritmos de aproximação, Teoria dos grafos - BV FAPESP
Advanced search
Start date
Betweenand

Algorithmic and structural aspects of Covering and Packing problems on graphs

Grant number: 16/21250-3
Support Opportunities:Scholarships in Brazil - Post-Doctoral
Start date: April 01, 2017
End date: October 13, 2019
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Agreement: Coordination of Improvement of Higher Education Personnel (CAPES)
Principal Investigator:Flávio Keidi Miyazawa
Grantee:Phablo Fernando Soares Moura
Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
Associated scholarship(s):17/22611-2 - Algorithmic and structural aspects of covering and packing problems on graphs, BE.EP.PD

Abstract

This is the post-doctoral research proposal of Phablo F. S. Moura, to be developed under supervision of professor Flávio K. Miyazawa, at Instituto de Computação of Universidade Estadual de Campinas (UNICAMP).The project lies in the fields of algorithms and graph theory, and focuses on covering and packing problems on graphs. In this project, we plan to investigate the following problems.The first one consists in partitioning (i.e. covering and packing) the set of vertices of a graph in such a way that each part induces a connected subgraph, and all parts are balanced, that is, the weight of the lightest part is maximized. In the second problem, we are interested in covering the set of vertices of a graph with a minimum number of paths.This generalizes the classical Hamilton path problem.The third problem presented in this proposal is related to a long-standing conjecture which deals with finding sufficient conditions for every directed graph to contain, as a subgraph, a subdivision of a given directed 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 (6)
(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)
LINTZMAYER, CARLA N.; MIYAZAWA, FLAVIO K.; MOURA, PHABLO F. S.; XAVIER, EDUARDO C.. Randomized approximation scheme for Steiner Multi Cycle in the Euclidean plane. THEORETICAL COMPUTER SCIENCE, v. 835, p. 134-155, . (16/23552-7, 16/21250-3, 17/22611-2, 15/11937-9, 16/01860-1)
MOURA, PHABLO F. S.; WAKABAYASHI, YOSHIKO. Strong intractability results for generalized convex recoloring problems. DISCRETE APPLIED MATHEMATICS, v. 281, n. SI, p. 252-260, . (16/21250-3, 17/22611-2, 15/11937-9)
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)
MIYAZAWA, FLAVIO K.; MOURA, PHABLO F. S.; OTA, MATHEUS J.; WAKABAYASHI, YOSHIKO. Partitioning a graph into balanced connected classes: Formulations, separation and experiments. European Journal of Operational Research, v. 293, n. 3, p. 11-pg., . (16/21250-3, 15/11937-9, 17/22611-2, 16/01860-1)
MOURA, PHABLO F. S.; WAKABAYASHI, YOSHIKO. Strong intractability results for generalized convex recoloring problems. DISCRETE APPLIED MATHEMATICS, v. 281, p. 9-pg., . (16/21250-3, 15/11937-9, 17/22611-2)
LINTZMAYER, CARLA N.; MIYAZAWA, FLAVIO K.; MOURA, PHABLO F. S.; XAVIER, EDUARDO C.. Quasilinear Approximation Scheme for Steiner Multi Cycle in the Euclidean plane. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, v. 346, p. 13-pg., . (15/11937-9, 17/22611-2, 16/23552-7, 16/01860-1, 16/21250-3)