Advanced search
Start date
Betweenand

Graph transversals

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:
Articles published in other media outlets (0 total):
More itemsLess items
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

Scientific publications
(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)
BOTLER, FABIO; FERNANDES, CRISTINA G.; GUTIERREZ, JUAN. On Tuza's conjecture for triangulations and graphs with small treewidth. DISCRETE MATHEMATICS, v. 344, n. 4, . (13/03447-6, 15/08538-5)
GUTIERREZ, JUAN. ransversals of longest cycles in partial k-trees and chordal graph. JOURNAL OF GRAPH THEORY, v. 98, n. 4, . (15/08538-5)
CERIOLI, MARCIA R.; FERNANDES, CRISTINA G.; GOMEZ, RENZO; GUTIERREZ, JUAN; LIMA, PALOMA T.. Transversals of longest paths. DISCRETE MATHEMATICS, v. 343, n. 3, . (13/03447-6, 15/08538-5)
Academic Publications
(References retrieved automatically from State of São Paulo Research Institutions)
ALVA, Juan Gabriel Gutierrez. Transversals of graphs. 2018. Doctoral Thesis - Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) São Paulo.

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