Abstract
The Hamiltonian Cycle problem asks if an n-vertex graph G has a cycle passing through all vertices of G. This problem is a classic NP-complete problem. So far, finding an exact algorithm that solves it in O *(α n) time for some constant α< 2 is a notorious open problem. For a claw-free graph G, finding a hamiltonian cycle is equivalent to finding a closed trail (eulerian subgraph) that dominates the edges of some associated graph H. Using this translation we obtain two exact algorithms that solve the Hamiltonian Cycle problem for the class of claw-free graphs: one algorithm that uses O *(1.6818n) time and exponential space, and one algorithm that uses O *(1.8878n) time and polynomial space.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bax, E.T.: Inclusion and exclusion algorithm for the Hamiltonian path problem. Information Processing Letters 47, 203–207 (1993)
Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: The travelling salesman problem in bounded degree graphs. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 198–209. Springer, Heidelberg (2008)
Broersma, H.J., Paulusma, D.: Computing sharp 2-factors in claw-free graphs. In: Ochmański, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol. 5162, pp. 193–204. Springer, Heidelberg (2008)
Diestel, R.: Graph Theory, 2nd edn. Graduate Texts in Mathematics, vol. 173. Springer, Heidelberg (2000)
Eppstein, D.: The traveling salesman problem for cubic graphs. Journal of Graph Algorithms and Applications 11, 61–81 (2007)
Faudree, R., Flandrin, E., Ryjáček, Z.: Claw-free graphs—a survey. Discrete Mathematics 164, 87–147 (1997)
Garey, M.R., Johnson, D.S.: Computers and Intractability. W.H. Freeman and Co., New York (1979)
Gebauer, H.: On the number of hamilton cycles in bounded degree graphs. In: 4th Workshop on Analytic and Combinatorics (ANALCO 2008), SIAM, Philadelphia (2008)
Harary, F.: Graph Theory. Addison-Wesley, Reading (1969)
Harary, F., Nash-Williams, C.S.J.A.: On eulerian and hamiltonian graphs and line graphs. Canadian Mathematical Bulletin 8, 701–709 (1965)
Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. Journal of SIAM 10, 196–210 (1962)
Iwama, K., Nakashima, T.: An improved exact algorithm for cubic graph TSP. In: Lin, G. (ed.) COCOON 2007. LNCS, vol. 4598, pp. 108–117. Springer, Heidelberg (2007)
Karp, R.M.: Dynamic programming meets the principle of inclusion and exclusion. Operations Research Letters 1, 49–51 (1982)
Li, M., Corneil, D.G., Mendelsohn, E.: Pancyclicity and NP-completeness in planar graphs. Discrete Applied Mathematics 98, 219–225 (2000)
Müller, H.: Hamiltonian circuits in chordal bipartite graphs. Discrete Mathematics 156, 291–298 (1996)
Roussopoulos, N.D.: A max {m,n} algorithm for determining the graph H from its line graph G. Information Processing Letters 2, 108–112 (1973)
Ryjáček, Z.: On a closure concept in claw-free graphs. Journal of Combinatorial Theory, series B 70, 217–224 (1997)
Thomassen, C., Toft, B.: Non-separating induced cycles in graphs. Journal of Combinatorial Theory, Series B 31, 199–224 (1981)
Woeginger, G.J.: Open problems around exact algorithms. Discrete Applied Mathematics 156, 397–405 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Broersma, H., Fomin, F.V., van ’t Hof, P., Paulusma, D. (2010). Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs. In: Paul, C., Habib, M. (eds) Graph-Theoretic Concepts in Computer Science. WG 2009. Lecture Notes in Computer Science, vol 5911. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11409-0_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-11409-0_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11408-3
Online ISBN: 978-3-642-11409-0
eBook Packages: Computer ScienceComputer Science (R0)