Fast exact algorithms for hamiltonicity in claw-free graphs

Haitze J. Broersma, Fedor V. Fomin, Pim van 't Hof, Daniël Paulusma

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

8 Citations (Scopus)
1 Downloads (Pure)


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^*(\aplha^n)$ time for some constant $\alpha < 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.6818^n)$ time and exponential space, and one algorithm that uses $O^*(1.8878^n)$ time and polynomial space.
Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science
Subtitle of host publication35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009. Revised Papers
EditorsChristophe Paul, Michel Habib
Place of PublicationBerlin
Number of pages10
ISBN (Electronic)978-3-642-11409-0
ISBN (Print)978-3-642-11408-3
Publication statusPublished - Feb 2010
Event35th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2009 - Montpellier, France
Duration: 24 Jun 200926 Jun 2009
Conference number: 35

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference35th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2009
Abbreviated titleWG

Cite this