Scholarship 17/22611-2 - Teoria dos grafos - BV FAPESP
Advanced search
Start date
Betweenand

Algorithmic and structural aspects of covering and packing problems on graphs

Grant number: 17/22611-2
Support Opportunities:Scholarships abroad - Research Internship - Post-doctor
Start date: October 01, 2018
End date: September 30, 2019
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Flávio Keidi Miyazawa
Grantee:Phablo Fernando Soares Moura
Supervisor: Zdenek Dvorak
Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
Institution abroad: Charles University in Prague (CU), Czech Republic  
Associated to the scholarship:16/21250-3 - Algorithmic and structural aspects of Covering and Packing problems on graphs, BP.PD

Abstract

This is a proposal for a research internship of Phablo Fernando Soares Moura (FAPESP Proc. 2016/21250-3), postdoctoral researcher under supervision of Professor Flávio Keidi Miyazawa at the Instituto de Computação at Universidade Estadual de Campinas. This internship, to be held at Charles University in Prague, the Czech Republic, is planned from August 1, 2018 to July 31, 2019 (12 months). During this period, Phablo will be supervised by Professor Zdenek Dvorak. The focus of this research proposal is the study of covering and packing problems on graphs and digraphs. We are particularly interested in studying the path cover problem, the Four-Color problem, and problems concerning the Mader's conjecture about subdivisions of digraphs. In the first problem, we are interested in covering the set of vertices of a graph into a minimum number of vertex-disjoint paths. In the second problem, we study the reducibility of configurations for the Four-Color theorem. Finally, in the context of Mader's conjecture, we aim to find sufficient conditions for a digraph to contain an acyclic digraph as a subdivision.

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)