Busca avançada
Ano de início
Entree

Transversais em grafos

Processo: 15/08538-5
Modalidade de apoio:Bolsas no Brasil - Doutorado
Vigência (Início): 01 de setembro de 2015
Vigência (Término): 31 de agosto de 2018
Área do 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.

Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa:
Matéria(s) publicada(s) em Outras Mídias (0 total):
Mais itensMenos itens
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

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., . (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)
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., . (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., . (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)
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)
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.

Por favor, reporte erros na lista de publicações científicas utilizando este formulário.