Fast exact algorithms for hamiltonicity in claw-free graphs


Broersma, Hajo and Fomin, Fedor V. and Hof, Pim van 't and Paulusma, Daniël (2010) Fast exact algorithms for hamiltonicity in claw-free graphs. In: 35th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2009, 24-26 June 2009, Montpellier, France (pp. pp. 44-53).

[img] PDF
Restricted to UT campus only
: Request a copy
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.
Item Type:Conference or Workshop Item
Copyright:© 2010 Springer
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page