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

7 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 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
PublisherSpringer
Pages44-53
Number of pages10
ISBN (Electronic)978-3-642-11409-0
ISBN (Print)978-3-642-11408-3
DOIs
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
Volume5911
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference35th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2009
Abbreviated titleWG
CountryFrance
CityMontpellier
Period24/06/0926/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