### Abstract

Original language | Undefined |
---|---|

Pages (from-to) | 129-145 |

Number of pages | 17 |

Journal | Algorithmica |

Volume | 65 |

Issue number | 1 |

DOIs | |

Publication status | Published - 2013 |

### Keywords

- EWI-21076
- MSC-05C
- (Hamilton) cycle
- Exact algorithm
- IR-86129
- NP-complete
- NP-hard
- Hamiltonian graph
- METIS-297586
- Computational Complexity

### Cite this

*Algorithmica*,

*65*(1), 129-145. https://doi.org/10.1007/s00453-011-9576-4

}

*Algorithmica*, vol. 65, no. 1, pp. 129-145. https://doi.org/10.1007/s00453-011-9576-4

**Exact algorithms for finding longest cycles in claw-free graphs.** / Broersma, Haitze J.; Fomin, Fedor V.; van 't Hof, Pim; Paulusma, Daniël.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

T1 - Exact algorithms for finding longest cycles in claw-free graphs

AU - Broersma, Haitze J.

AU - Fomin, Fedor V.

AU - van 't Hof, Pim

AU - Paulusma, Daniël

N1 - eemcs-eprint-21076

PY - 2013

Y1 - 2013

N2 - The Hamiltonian Cycle problem is the problem of deciding whether an n-vertex graph G has a cycle passing through all vertices of G. This problem is a classic NP-complete problem. Finding an exact algorithm that solves it in (n) time for some constant α<2 was a notorious open problem until very recently, when Björklund presented a randomized algorithm that uses (1657n) time and polynomial space. The Longest Cycle problem, in which the task is to find a cycle of maximum length, is a natural generalization of the Hamiltonian Cycle problem. For a claw-free graph G, finding a longest cycle is equivalent to finding a closed trail (i.e., a connected even subgraph, possibly consisting of a single vertex) that dominates the largest number of edges of some associated graph H. Using this translation we obtain two deterministic algorithms that solve the Longest Cycle problem, and consequently the Hamiltonian Cycle problem, for claw-free graphs: one algorithm that uses (16818n) time and exponential space, and one algorithm that uses (18878n) time and polynomial space.

AB - The Hamiltonian Cycle problem is the problem of deciding whether an n-vertex graph G has a cycle passing through all vertices of G. This problem is a classic NP-complete problem. Finding an exact algorithm that solves it in (n) time for some constant α<2 was a notorious open problem until very recently, when Björklund presented a randomized algorithm that uses (1657n) time and polynomial space. The Longest Cycle problem, in which the task is to find a cycle of maximum length, is a natural generalization of the Hamiltonian Cycle problem. For a claw-free graph G, finding a longest cycle is equivalent to finding a closed trail (i.e., a connected even subgraph, possibly consisting of a single vertex) that dominates the largest number of edges of some associated graph H. Using this translation we obtain two deterministic algorithms that solve the Longest Cycle problem, and consequently the Hamiltonian Cycle problem, for claw-free graphs: one algorithm that uses (16818n) time and exponential space, and one algorithm that uses (18878n) time and polynomial space.

KW - EWI-21076

KW - MSC-05C

KW - (Hamilton) cycle

KW - Exact algorithm

KW - IR-86129

KW - NP-complete

KW - NP-hard

KW - Hamiltonian graph

KW - METIS-297586

KW - Computational Complexity

U2 - 10.1007/s00453-011-9576-4

DO - 10.1007/s00453-011-9576-4

M3 - Article

VL - 65

SP - 129

EP - 145

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 1

ER -