Accession Number:

ADA237241

Title:

AN Exact Algorithm for Finding Undirected Hamiltonian Cycles Based on a Two-Matching Problem Relaxation

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Report Date:

1991-03-22

Pagination or Media Count:

13.0

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 knights tour problems having up to 10,000 vertices.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE