AN Exact Algorithm for Finding Undirected Hamiltonian Cycles Based on a Two-Matching Problem Relaxation
Donald L. Miller, Joseph F. Pekny, Gerald L. Thompson · 1991
Abstract : We describe an algorithm for finding two matchings in undirected graphs. This algorithm is used as a basis for a simple exact algorithm for determining the hamiltonicity of undirected graphs. Results are presented for random graphs with up to 30,000 vertices and for knight's tour problems having up to 10,000 vertices.