An Exhaustive Search Algorithm for Finding Hamiltonian Cycles
Date
1980
Authors
Zeps, Dainis
Journal Title
Journal ISSN
Volume Title
Publisher
EIK,Elektronische Informationsverarbeitung und Kybernetik, Universität Trier, Akademie Verlag
Abstract
The paper suggests an exhaustive search algorithm for finding
Hamiltonian circuits in an undirected graph based on depth-first
search and working successfully on sparse graphs. The method is
based on the idea not to search all palms in the graphs but only
those which are not branched.
Tutte's 46 vertices graph searching took less than 3 minutes on EC-
1022 computer.
Description
Keywords
graph theory , hamiltonian cycle , depth-first search , palm tree
Citation
EIK 16(1-3): 69-75 (1980)