Open AccessCaminhos mais longos em grafos
Author(s) -
Susanna F. de Rezende,
Yoshiko Wakabayashi
Publication year - 2015
Language(s) - Portuguese
Resource type - Conference proceedings
DOI - 10.5753/ctd.2015.10001
Subject(s) - biology , humanities , philosophy
Neste trabalho, estudamos problemas sobre caminhos mais longos em grafos tanto do ponto de vista estrutural quanto algorítmico. A primeira parte tem como foco o estudo de problemas motivados pela seguinte questão levantada por T. Gallai em 1966: todo grafo conexo contém um vértice comum a todos os seus caminhos mais longos? Discutimos brevemente alguns resultados da literatura acerca desses problemas e apresentamos nossas contribuições. Na segunda parte, investigamos o problema de encontrar um caminho mais longo em um grafo, o qual é NP-difícil para grafos arbitrários. Uma versão completa dos resultados apresentados neste resumo pode ser encontrada em [de Rezende 2014].