Exact Algorithm for Funding Undirected Hamiltonian Cycles Based on a Two-MatchingProblem Relaxation

摘要

We describe an algorithm for funding two matchings in undirected graphs. Thisalgorithm 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.