Algorithmic and structural aspects of covering and packing problems on graphs
Spectral analysis to anomaly detection in dynamic attributed graphs
Decomposition of a graph into paths: structural and algorithmic aspects
| Grant number: | 15/08538-5 |
| Support type: | Scholarships in Brazil - Doctorate |
| Effective date (Start): | September 01, 2015 |
| Effective date (End): | August 31, 2018 |
| Field of knowledge: | Physical Sciences and Mathematics - Computer Science - Theory of Computation |
| Principal researcher: | Cristina Gomes Fernandes |
| Grantee: | Juan Gabriel Gutierrez Alva |
| Home Institution: | Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil |
| Associated research grant: | 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science, AP.TEM |
Abstract In graph theory, a classic problem consists in finding a set of vertex or edges such that every object of some kind contains at least one element in that set. Such a set is called transversal, and in general we try to search little transversals, possibly of minimum size.When we don't know the size of a minimum transversal, it is interesting to search for good delimitations for that size. When finding a minimum transversal is NP-hard, we try to find approximations for the problem. The target of this project are some kinds of transversals in graphs, for example transversal of longest paths, of longest cycles, of odd-cycles, and maximal cliques. The goal is to find the size of minimum transversals for these objects in arbitrary or specific classes of graphs. | |
| News published in Agência FAPESP Newsletter about the scholarship: | |
| TITULO | |
| Articles published in other media outlets (0 total): | |
| More itemsLess items | |
| VEICULO: TITULO (DATA) | |
| VEICULO: TITULO (DATA) | |