Caminhos mais longos em grafos

• Susanna de Rezende KTH Royal Institute of Technology
• Yoshiko Wakabayashi USP

DOI: https://doi.org/10.5753/ctd.2015.10001

Abstract

The central theme of this paper is the study of problems related to longest paths in graphs, both from a structural and an algorithmic point of view. The first part focuses on the study of problems motivated by the following question raised by T. Gallai in 1966: does every connected graph have a vertex common to all its longest paths? We briefly discuss known results and present our contributions. In the second part, we investigate the problem of finding a longest path in a graph, which is NP-hard for arbitrary graphs. A full account of the results presented in this paper can be found in [de Rezende 2014].

References

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.