Caminhos mais longos em grafos (2015)
- Authors:
- Autor USP: WAKABAYASHI, YOSHIKO - IME
- Unidade: IME
- DOI: 10.5753/ctd.2015.10001
- Assunto: TEORIA DOS GRAFOS
- Agências de fomento:
- Language: Português
- Abstract: 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].
- Imprenta:
- Publisher: SBC
- Publisher place: Porto Alegre
- Date published: 2015
- Source:
- Título: Anais
- Conference titles: Congresso da Sociedade Brasileira de Computação - CSBC
- Este periódico é de assinatura
- Este artigo é de acesso aberto
- URL de acesso aberto
- Cor do Acesso Aberto: bronze
-
ABNT
REZENDE, Susanna F. de e WAKABAYASHI, Yoshiko. Caminhos mais longos em grafos. 2015, Anais.. Porto Alegre: SBC, 2015. Disponível em: https://doi.org/10.5753/ctd.2015.10001. Acesso em: 09 out. 2024. -
APA
Rezende, S. F. de, & Wakabayashi, Y. (2015). Caminhos mais longos em grafos. In Anais. Porto Alegre: SBC. doi:10.5753/ctd.2015.10001 -
NLM
Rezende SF de, Wakabayashi Y. Caminhos mais longos em grafos [Internet]. Anais. 2015 ;[citado 2024 out. 09 ] Available from: https://doi.org/10.5753/ctd.2015.10001 -
Vancouver
Rezende SF de, Wakabayashi Y. Caminhos mais longos em grafos [Internet]. Anais. 2015 ;[citado 2024 out. 09 ] Available from: https://doi.org/10.5753/ctd.2015.10001 - Um algoritmo híbrido para o problema de corte unidimensional
- Contribuições a teoria dos grafos e otimização combinatória
- Two-and three-dimensional parametric packing
- Composition of facets of the clique partitioning polytope
- On the circuit cover problem for mixed graphs
- Near-optimum universal graphs for graphs with bounded degrees
- The maximum agreement forest problem: approximation algorithms and computational experiments
- Covering a graph with nontrivial vertex-disjoint paths: existence and optimization
- Tree 3-spanners on generalized prisms of graphs
- Sobre grafos hamiltonianos
Informações sobre o DOI: 10.5753/ctd.2015.10001 (Fonte: oaDOI API)
Download do texto completo
Tipo | Nome | Link | |
---|---|---|---|
3200013.pdf | Direct link |
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas