Skip to main content

Research Repository

Advanced Search

Exact algorithms for finding longest cycles in claw-free graphs

Broersma, H.J.; Fomin, F.V.; Hof van 't, P.; Paulusma, D.

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


Authors

H.J. Broersma

F.V. Fomin

P. Hof van 't



Abstract

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 O*(an)(n) time for some constant α<2 was a notorious open problem until very recently, when Björklund presented a randomized algorithm that uses O*(1.657n)(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 O*(1.6818n)(16818n) time and exponential space, and one algorithm that uses O*(1.8878n)(18878n) time and polynomial space.

Citation

Broersma, H., Fomin, F., Hof van 't, P., & Paulusma, D. (2013). Exact algorithms for finding longest cycles in claw-free graphs. Algorithmica, 65(1), 129 -145. https://doi.org/10.1007/s00453-011-9576-4

Journal Article Type Article
Publication Date Jan 1, 2013
Deposit Date Dec 6, 2011
Publicly Available Date Mar 28, 2012
Journal Algorithmica
Print ISSN 0178-4617
Electronic ISSN 1432-0541
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 65
Issue 1
Pages 129 -145
DOI https://doi.org/10.1007/s00453-011-9576-4
Public URL https://durham-repository.worktribe.com/output/1502674

Files

Accepted Journal Article (260 Kb)
PDF

Copyright Statement
The original publication is available at www.springerlink.com





You might also like



Downloadable Citations