We are struggling to understand a fast algorithm for finding Hamiltonian cycle (for random graphs) due to Prof. Alan Frieze* and see whether that algorithm could be implemented efficiently. If there is an open source implementation of the algorithm, we can contribute to the testing of that code.We have a graph which has at least 10 Hamiltonian Cycles and we want to use that to find a specific Hamiltonian Cycle (How easy/hard is that will be our question).
Abstract of Broder et al's paper (from citeseer: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.1661 )
Consider a random graph G composed of a Hamiltonian cycle on n labeled vertices and dn random edges that "hide" the cycle. Is it possible to unravel the structure, that is, to efficiently find a Hamiltonian cycle in G? We describe an O(n 3 log n) steps algorithm A for this purpose, and prove that it succeeds almost surely. Part one of A properly covers the "trouble spots" of G by a collection of disjoint paths. (This is the hard part to analyze.) Part two of A extends this cover to a full cycle by the rotation-extension technique which is already classical for such problems.
qn1) Has any one implemented Broder et al's algorithm?
qn 2) Are there recent paper better than Broder et al's algorithm –
qn 3) If there are 10 to 15 Hamiltonian cycles in a graph do their algorithm find all of them fast? –
- A. Broder, A. M. Frieze and E. Shamir, "Finding hidden Hamiltonian Cycle," Random Structures and Algorithms , 5, 2006