Combinatorics and Graph Theory


Polynomial Algorithms for Shortest Hamiltonian Path and Circuit

Authors: Dhananjay P. Mehendale

The problem of finding shortest Hamiltonian path and shortest Hamiltonian circuit in a weighted complete graph belongs to the class of NP-Complete problems [1]. This well known problem asks for a method or algorithm to locate such path or circuit that passes through every vertex only once in the given weighted complete graph. In this paper we begin with proposing two approximation algorithms for shortest Hamiltonian graphs which essentially consists of applying certain chosen permutations (transpositions or product of transpositions) on the adjacency matrix of given weighted complete graph causing reshuffling of the labels of its vertices. We change the labels of vertices through proper choice of permutations in such a way that in this relabeled graph the Hamiltonian path 123….k(k+1)…p becomes approximation to shortest path in the given weighted complete graph under consideration. We then define so called ordered weighted adjacency list for given weighted complete graph and proceed to the main result of the paper, namely, the exact algorithm based on utilization of ordered weighted adjacency list and the simple properties that any path or circuit must satisfy. This algorithm performs checking of sub-lists, containing (n-1) entries (edge pairs) for paths and n entries (edge pairs) for circuits, chosen from ordered adjacency list in a well defined sequence to determine exactly the shortest Hamiltonian path and shortest Hamiltonian circuit. The procedure has intrinsic advantage of landing on the desired solution in quickest possible time and even in worst case in polynomial time.

Comments: 14 Pages

Download: PDF

Submission history

[v1] 2013-04-01 07:25:24
[v2] 2013-04-11 15:24:12

Unique-IP document downloads: 2371 times is a pre-print repository rather than a journal. Articles hosted may not yet have been verified by peer-review and should be treated as preliminary. In particular, anything that appears to include financial or legal advice or proposed medical treatments should be treated with due caution. will not be responsible for any consequences of actions that result from any form of use of any documents on this website.

Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.

comments powered by Disqus