Exact Algorithms for Finding Longest Cycles in Claw-Free Graphs

Exact Algorithms for Finding Longest Cycles in Claw-Free Graphs

0.00 Avg rating0 Votes
Article ID: iaor2013301
Volume: 65
Issue: 1
Start Page Number: 129
End Page Number: 145
Publication Date: Jan 2013
Journal: Algorithmica
Authors: , , ,
Keywords: graphs
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 𝒪 * ( α n ) equ1 time for some constant α <2 was a notorious open problem until very recently, when Björklund presented a randomized algorithm that uses 𝒪 * ( 1.657 n ) equ2 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 𝒪 * ( 1.6818 n ) equ3 time and exponential space, and one algorithm that uses 𝒪 * ( 1.8878 n ) equ4 time and polynomial space.

Reviews

Required fields are marked *. Your email address will not be published.