### Abstract

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 |

### Fingerprint

### Keywords

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

### Cite this

*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

}

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

**Fast exact algorithms for hamiltonicity in claw-free graphs.** / Broersma, Haitze J.; Fomin, Fedor V.; van 't Hof, Pim; Paulusma, Daniël.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Fast exact algorithms for hamiltonicity in claw-free graphs

AU - Broersma, Haitze J.

AU - Fomin, Fedor V.

AU - van 't Hof, Pim

AU - Paulusma, Daniël

N1 - 10.1007/978-3-642-11409-0_4

PY - 2010/2

Y1 - 2010/2

N2 - 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.

AB - 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.

KW - IR-71167

KW - EWI-17828

KW - METIS-270799

U2 - 10.1007/978-3-642-11409-0_4

DO - 10.1007/978-3-642-11409-0_4

M3 - Conference contribution

SN - 978-3-642-11408-3

T3 - Lecture Notes in Computer Science

SP - 44

EP - 53

BT - Graph-Theoretic Concepts in Computer Science

A2 - Paul, Christophe

A2 - Habib, Michel

PB - Springer

CY - Berlin

ER -