Busca avançada
Ano de início
Entree

Transversais em grafos

Processo: 15/08538-5
Linha de fomento: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

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
(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)
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)
GUTIERREZ, JUAN. ransversals of longest cycles in partial k-trees and chordal graph. JOURNAL OF GRAPH THEORY, v. 98, n. 4, . (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 escrevendo para: cdi@fapesp.br.