Transversais em grafos

• Processo: 15/08538-5
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Data de Início da vigência: 01 de setembro de 2015
• Data de Término da vigência: 31 de agosto de 2018
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Cristina Gomes Fernandes
• Beneficiário: Juan Gabriel Gutierrez Alva
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Vinculado ao auxílio: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação, AP.TEM
• Assunto(s): Teoria dos grafos Grafos Algoritmos
• Palavra(s)-Chave do Pesquisador: Algoritmos | grafos | transversais | Teoria dos grafos

Resumo

Na área de teoria dos grafos, um problema clássico consiste em encontrar um conjunto de vértices ou arestastais que todo objeto de certo tipo no grafo contém pelo menos um elemento nesse conjunto. Um tal conjunto échamado de transversal, e em geral buscam-se transversais pequenas, possivelmente de tamanho mínimo. Quando não se conhece o tamanho de uma transversal mínima, naturalmente torna-se interessante a busca por boasdelimitações para esse tamanho. Quando encontrar uma transversal mínima é um problema NP-difícil, buscam-se aproximações para o problema. O foco deste projeto são alguns tipos de transversais em grafos, como por exemplo transversais de caminhos mais longos, de circuitos mais longos, de circuitos ímpares e transversais de cliques maximais. O objetivo é a determinação do tamanho de transversais mínimas para estes objetos senão em grafos arbitrários, em classes específicas de grafos.

Publicações científicas

(6)

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

GUTIERREZ, JUAN; BENDER, MA; FARACHCOLTON, M; MOSTEIRO, MA. Transversals of Longest Cycles in Chordal and Bounded Tree-Width Graphs. LATIN 2018: THEORETICAL INFORMATICS, v. 10807, p. 14-pg., 2018-01-01. (15/08538-5)

GUTIERREZ, JUAN. ransversals of longest cycles in partial k-trees and chordal graph. JOURNAL OF GRAPH THEORY, v. 98, n. 4, JUL 2021. (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, MAR 2020. (13/03447-6, 15/08538-5)

BOTLER, FABIO; FERNANDES, CRISTINA G.; GUTIERREZ, JUAN. On Tuza's conjecture for triangulations and graphs with small treewidth. DISCRETE MATHEMATICS, v. 344, n. 4, APR 2021. (13/03447-6, 15/08538-5)

GUTIERREZ, JUAN. All longest cycles in a 2-connected partial 3-tree share a common vertex. JOURNAL OF GRAPH THEORY, v. 103, n. 4, p. 23-pg., 2023-03-01. (15/08538-5)

BOTLER, F.; FERNANDES, C. G.; GUTIERREZ, J.. On Tuza's Conjecture for Triangulations and Graphs with Small Treewidth. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, v. 346, p. 13-pg., 2019-08-30. (15/08538-5)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

ALVA, Juan Gabriel Gutierrez. Transversals of graphs. 2018. Tese de Doutorado - Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) São Paulo.