AN Exact Algorithm for Finding Undirected Hamiltonian Cycles Based on a Two-Matching Problem Relaxation
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
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 knights tour problems having up to 10,000 vertices.
- Numerical Mathematics