I. Pohl and L. Stockmeyer (USA)
Hamiltonian path, longest path heuristics, Pohl-Warnsdorf heuristic
Two new series of graphs are introduced. Properties of these graphs make them suitable as test beds for Hamil tonian path heuristics. The graphs are planar and regular of degree 3, and each series has a simple recursive definition. These graphs are "conceptual adversaries" to methods that try to exploit local characteristics. For each series, we give an analysis showing that the number of Hamiltonian paths in these graphs grows polynomially in the number of nodes of the graph.
Important Links:
Go Back
