Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

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

Broersma, H.J. and Fomin, F.V. and Hof van 't, P. and Paulusma, Daniel (2013) 'Exact algorithms for finding longest cycles in claw-free graphs.', Algorithmica., 65 (1). 129 -145.

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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
(255Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1007/s00453-011-9576-4
Publisher statement:The original publication is available at www.springerlink.com
Date accepted:No date available
Date deposited:28 March 2012
Date of first online publication:January 2013
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar