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

Title of host publication | Graph-Theoretic Concepts in Computer Science |

Subtitle of host publication | 35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009. Revised Papers |

Editors | Christophe Paul, Michel Habib |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 44-53 |

Number of pages | 10 |

ISBN (Electronic) | 978-3-642-11409-0 |

ISBN (Print) | 978-3-642-11408-3 |

DOIs | |

Publication status | Published - Feb 2010 |

Event | 35th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2009 - Montpellier, France Duration: 24 Jun 2009 → 26 Jun 2009 Conference number: 35 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer Verlag |

Volume | 5911 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 35th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2009 |
---|---|

Abbreviated title | WG |

Country | France |

City | Montpellier |

Period | 24/06/09 → 26/06/09 |

### Keywords

- IR-71167
- EWI-17828
- METIS-270799

## Fingerprint Dive into the research topics of 'Fast exact algorithms for hamiltonicity in claw-free graphs'. Together they form a unique fingerprint.

## Cite this

Broersma, H. J., Fomin, F. V., van 't Hof, P., & Paulusma, D. (2010). Fast exact algorithms for hamiltonicity in claw-free graphs. In C. Paul, & M. Habib (Eds.),

*Graph-Theoretic Concepts in Computer Science: 35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009. Revised Papers*(pp. 44-53). (Lecture Notes in Computer Science; Vol. 5911). Berlin: Springer. https://doi.org/10.1007/978-3-642-11409-0_4