An Analysis of Extreme Hamiltonian Circuits.
Abstract
The report investigates the problem of finding the shortest and longest Hamiltonian circuits on a complete graph, having finitely many vertices. Analytic conditions, involving sets of inequalities between edge lengths-which the authors call edgeconvexity- are given which lead to minimal and maximal circuits. Geometric realizations of this condition are given, which include convex polygons in the Euclidean plane and on the two-sphere. Other realizations include convex polygons in the plane where distance is measured with any linear (Minkowski) metric; points on rectifiable Jordan curve, where distance is measured by minor arc length; points in a Minkowski plane, distance measured with the Minkowski metric, where there is a minimal Hamiltonian circuit (H-circuit) whose length equals that of the perimeter of the convex hull of the set of points. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 31, 1972
- Accession Number
- AD0754842
Entities
People
- Kenneth Kalmanson
Organizations
- Montclair State University