Algorithmic and structural aspects of Covering and Packing problems on graphs
Algorithmic and structural aspects of covering and packing problems on graphs
Development of analytical tools in collaboration with the PDS team and the RepMus ...
Grant number: | 11/08033-0 |
Support Opportunities: | Scholarships in Brazil - Doctorate |
Start date: | August 01, 2011 |
End date: | February 29, 2016 |
Field of knowledge: | Physical Sciences and Mathematics - Computer Science - Theory of Computation |
Principal Investigator: | Yoshiko Wakabayashi |
Grantee: | Fábio Happ Botler |
Host Institution: | Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil |
Associated scholarship(s): | 14/01460-8 - Graph decompositions, BE.EP.DR |
Abstract The focus of this project is a classical problem in graph theory on the partition of the edge set of a graph into a minimum number of paths. This problem has its roots in a conjecture of Gallai (1966) on an upper bound for this number that depends only on the number of vertices of the graph. This conjecture states that the edge set of an n-vertex connected graph can be decomposed into at most (n+1)/2 paths. Not so many results have been published on this conjecture. It is known that it has been established for graphs in which all vertices have odd degree, and also for graphs in which the vertices of even degree induce a subgraph with a special structure. We are interested in investigating this conjecture for other classes of graphs and and also explore algorithmic aspects of this problem. Algorithmic results on this problem have not been found in the literature. | |
News published in Agência FAPESP Newsletter about the scholarship: | |
More itemsLess items | |
TITULO | |
Articles published in other media outlets ( ): | |
More itemsLess items | |
VEICULO: TITULO (DATA) | |
VEICULO: TITULO (DATA) | |