×

zbMATH — the first resource for mathematics

Algorithms for long paths in graphs. (English) Zbl 1117.68057
Summary: We obtain a polynomial algorithm in \(O(nm)\) time to find a long path in any graph with \(n\) vertices and \(m\) edges. The length of the path is bounded by a parameter defined on a neighborhood condition of any three independent vertices of the path. An example is given to show that this bound is better than several classic results.

MSC:
68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
05C38 Paths and cycles
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Albertson, M., Finding Hamiltonian cycles in ore graphs, Congr. numer., 58, 25-27, (1987)
[2] N. Alon, R. Yuster, U. Zwick, Color-coding: A new method for finding simple paths, cycles and other small subgraphs within large graphs, in: Proceedings of STOC, 1994, pp. 326-335 · Zbl 1344.68092
[3] C. Bazgan, M. Santha, Z. Tuza, On the approximability of finding a(nother) Hamiltonian cycles in cubic Hamiltonian graphs, in: Proceedings of STACS, 1998 · Zbl 0919.05039
[4] Bermond, J.-C., On Hamiltonian walks, Proc. fifth british combinatorial conference, Aberdeen, 1975, Util. math., 41-51, (1975)
[5] Bj√∂rklund, A.; Husfeldt, T., Finding a path of superlogarithmic length, SIAM J. comput., 32, 1395-1402, (2003) · Zbl 1041.68066
[6] Bodlaender, H.L., On linear time minor tests with depth-first search, J. algorithms, 14, 1-23, (1993) · Zbl 0764.68107
[7] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), Macmillan Press · Zbl 1134.05001
[8] Dirac, G.A., Some theorems on abstract graphs, Proc. London math. soc. (3), 2, 69-81, (1952) · Zbl 0047.17001
[9] T. Feder, R. Motwani, C.S. Subi, Finding long paths and cycles in sparse Hamiltonian graphs, in: Proceedings 32th STOC, 2000, pp. 524-529 · Zbl 1296.05114
[10] Flandrin, E.; Jung, H.A.; Li, H., Degree sum, neighbourhood intersections and hamiltonism, Discrete math., 90, 41-52, (1991) · Zbl 0746.05038
[11] Kocay, W.; Li, P.C., An algorithm for finding a long path in a graph, Util. math., 45, 169-185, (1994) · Zbl 0823.05052
[12] Korte, B.; Vygen, J., Combinatorial optimization: theory and algorithms, (2000), Springer-Verlag Berlin · Zbl 0953.90052
[13] Karger, D.; Motwani, R.; Ramkumar, G.D.S., On approximating the longest path in a graph, Algorithmica, 18, 82-98, (1997) · Zbl 0876.68083
[14] Monien, B., How to find long paths efficiently, Ann. discrete math., 239-254, (1985) · Zbl 0603.68069
[15] Ore, O., Note on Hamilton circuits, Amer. math. monthly, 67, 55, (1960) · Zbl 0089.39505
[16] S. Vishwanathan, An approximation algorithm for finding a long path in Hamiltonian graphs, in: Proceedings 11th SODA, 2000, pp. 680-685 · Zbl 0956.68111
[17] Wei, B., Longest cycles in 3-connected graphs, Discrete math., 170, 1-3, 195-201, (1997) · Zbl 0905.05042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.