Accession Number:

AD0754842

Title:

An Analysis of Extreme Hamiltonian Circuits.

Descriptive Note:

Technical rept.,

Corporate Author:

MONTCLAIR STATE COLL UPPER MONTCLAIR N J

Personal Author(s):

• Kalmanson,Kenneth

Report Date:

1972-10-31

Pagination or Media Count:

26.0

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

Descriptors:

• *OPERATIONS RESEARCH
• GRAPHICS
• CONVEX SETS
• TOPOLOGY
• THEOREMS

Subject Categories:

• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE