Output details

Exact algorithms for finding longest cycles in claw-free graphs

<12>A conference version appeared in the proceedings of WG 2009 (pp. 44-53). The paper has been cited in A. Björklund, Determinant Sums for Undirected Hamiltonicity, Proc. FOCS 2010, pp. 173-182, in which an exact but randomized algorithm for detecting hamiltonicity in general graphs was given. Björklund and Kaski (Counting closed trails, Information Processing Letters 113 (2013) 1-3) cites our paper as they used our framework together with the technique from Björklund, Husfeldt, Kaski and Koivisto, Computing the Tutte polynomial in vertex-exponential time, Proc. FOCS 2008, pp. 677-686, to obtain a faster algorithm for computing the length of a longest cycle in a claw-free graph.