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

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 22, 1991
Accession Number
ADA237241

Entities

People

  • D. L. Miller
  • Gerald L. Thompson
  • J. F. Pekny

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Energy and Power Technologies
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Chemical Engineering
  • Contracts
  • Engineering
  • Heuristic Methods
  • Mathematics
  • Military Research
  • Probability
  • Schools
  • Trees (Data Structures)
  • Universities

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research