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.

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 MAR 2020. Citações Web of Science: 0.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.