Caminhos mais longos em grafos

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].