# 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)

## 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^*(\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 language English Graph-Theoretic Concepts in Computer Science 35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009. Revised Papers Christophe Paul, Michel Habib Berlin Springer 44-53 10 978-3-642-11409-0 978-3-642-11408-3 https://doi.org/10.1007/978-3-642-11409-0_4 Published - Feb 2010 35th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2009 - Montpellier, FranceDuration: 24 Jun 2009 → 26 Jun 2009Conference number: 35

### Publication series

Name Lecture Notes in Computer Science Springer Verlag 5911 0302-9743 1611-3349

### Conference

Conference 35th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2009 WG France Montpellier 24/06/09 → 26/06/09