Caminhos mais longos em grafos
Resumo
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].
Referências
Alon, N., Yuster, R., and Zwick, U. (1995). Color-coding. J. ACM, 42(4):844–856.
Axenovich, M. (2009). When do three longest paths have a common vertex? Discrete Math. Algorithms Appl., 1:115–120.
Balister, P. N., Gy˝ori, E., Lehel, J., and Schelp, R. H. (2004). Longest paths in circular arc graphs. Combin. Probab. Comput., 13(3):311–317.
Björklund, A. and Husfeldt, T. (2003). Finding a path of superlogarithmic length. SIAM J. Comput., 32(6):1395–1402 (electronic).
de Rezende, S. F. (2014). Caminhos mais longos em grafos. Master’s thesis, Instituto de Matemática e Estatística, Universidade de São Paulo.
de Rezende, S. F., Fernandes, C. G., Martin, D. M., and Wakabayashi, Y. (2011). Intersection of longest paths in a graph. Electron. Notes Discrete Math., 38(0):743 – 748. The Sixth European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2011.
de Rezende, S. F., Fernandes, C. G., Martin, D. M., and Wakabayashi, Y. (2013). Intersecting longest paths. Discrete Math., 313(12):1401 – 1408.
Ehrenmüller, J., Fernandes, C. G., and Heise, C. G. (2013). Nonempty intersection of longest paths in series-parallel graphs. arXiv:1310.1376, submitted.
Erdos, P. and Katona, G., editors (1968). Theory of Graphs. Proceedings of the Colloquium held at Tihany, Hungary, September 1966. Academic Press, New York. Problem 4 (T. Gallai), p. 362.
Feder, T., Motwani, R., and Subi, C. (2002). Approximating the longest cycle problem in sparse graphs. SIAM J. Comput., 31(5):1596–1607.
Gabow, H. N. and Nie, S. (2008). Finding long paths, cycles and circuits. In Algorithms and Computation, volume 5369 of Lecture Notes in Comput. Sci., pages 752–763.
Garey, M. R. and Johnson, D. S. (1979). Computers and intractability. W. H. Freeman and Co., San Francisco, Calif. A guide to the theory of NP-completeness, A Series of Books in the Mathematical Sciences.
Grötschel, M. (1984). On Intersections of Longest Cycles. In Graph Theory and Combinatorics, pages 171–189. Academic Press.
Hippchen, T. (2008). Intersections of longest paths and cycles. Mathematics Theses, 80(Paper 53).
Joos, F. (2013). Longest paths in circular arc graphs. arXiv:1312.3075.
Karger, D., Motwani, R., and Ramkumar, G. D. S. (1997). On approximating the longest path in a graph. Algorithmica, 18(1):82–98.
Klavzar, S. and Petkovsek, M. (1990). Graphs with nonempty intersection of longest paths. Ars Combin., 29:43–52.
Monien, B. (1985). How to find long paths efficiently. Ann. Discrete Math., 25:239–254.
Rautenbach, D. and Sereni, J.-S. (2014). Transversals of longest paths and cycles.
SIAM J. Discrete Math., 28(1):335–341.
Skupién, Z. (1996). Smallest sets of longest paths with empty intersection. Combin. Probab. Comput., 5(4):429–436.
Walther, H. (1969). über die Nichtexistenz eines Knotenpunktes, durch den alle längsten Wege eines Graphen gehen. J. Combin. Theory, 6:1–6.
Axenovich, M. (2009). When do three longest paths have a common vertex? Discrete Math. Algorithms Appl., 1:115–120.
Balister, P. N., Gy˝ori, E., Lehel, J., and Schelp, R. H. (2004). Longest paths in circular arc graphs. Combin. Probab. Comput., 13(3):311–317.
Björklund, A. and Husfeldt, T. (2003). Finding a path of superlogarithmic length. SIAM J. Comput., 32(6):1395–1402 (electronic).
de Rezende, S. F. (2014). Caminhos mais longos em grafos. Master’s thesis, Instituto de Matemática e Estatística, Universidade de São Paulo.
de Rezende, S. F., Fernandes, C. G., Martin, D. M., and Wakabayashi, Y. (2011). Intersection of longest paths in a graph. Electron. Notes Discrete Math., 38(0):743 – 748. The Sixth European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2011.
de Rezende, S. F., Fernandes, C. G., Martin, D. M., and Wakabayashi, Y. (2013). Intersecting longest paths. Discrete Math., 313(12):1401 – 1408.
Ehrenmüller, J., Fernandes, C. G., and Heise, C. G. (2013). Nonempty intersection of longest paths in series-parallel graphs. arXiv:1310.1376, submitted.
Erdos, P. and Katona, G., editors (1968). Theory of Graphs. Proceedings of the Colloquium held at Tihany, Hungary, September 1966. Academic Press, New York. Problem 4 (T. Gallai), p. 362.
Feder, T., Motwani, R., and Subi, C. (2002). Approximating the longest cycle problem in sparse graphs. SIAM J. Comput., 31(5):1596–1607.
Gabow, H. N. and Nie, S. (2008). Finding long paths, cycles and circuits. In Algorithms and Computation, volume 5369 of Lecture Notes in Comput. Sci., pages 752–763.
Garey, M. R. and Johnson, D. S. (1979). Computers and intractability. W. H. Freeman and Co., San Francisco, Calif. A guide to the theory of NP-completeness, A Series of Books in the Mathematical Sciences.
Grötschel, M. (1984). On Intersections of Longest Cycles. In Graph Theory and Combinatorics, pages 171–189. Academic Press.
Hippchen, T. (2008). Intersections of longest paths and cycles. Mathematics Theses, 80(Paper 53).
Joos, F. (2013). Longest paths in circular arc graphs. arXiv:1312.3075.
Karger, D., Motwani, R., and Ramkumar, G. D. S. (1997). On approximating the longest path in a graph. Algorithmica, 18(1):82–98.
Klavzar, S. and Petkovsek, M. (1990). Graphs with nonempty intersection of longest paths. Ars Combin., 29:43–52.
Monien, B. (1985). How to find long paths efficiently. Ann. Discrete Math., 25:239–254.
Rautenbach, D. and Sereni, J.-S. (2014). Transversals of longest paths and cycles.
SIAM J. Discrete Math., 28(1):335–341.
Skupién, Z. (1996). Smallest sets of longest paths with empty intersection. Combin. Probab. Comput., 5(4):429–436.
Walther, H. (1969). über die Nichtexistenz eines Knotenpunktes, durch den alle längsten Wege eines Graphen gehen. J. Combin. Theory, 6:1–6.
Publicado
20/07/2015
Como Citar
DE REZENDE, Susanna; WAKABAYASHI, Yoshiko.
Caminhos mais longos em grafos. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 28. , 2015, Recife.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2015
.
p. 49-54.
ISSN 2763-8820.
DOI: https://doi.org/10.5753/ctd.2015.10001.
