Combinatorics and Graph Theory

1304 Submissions

[2] viXra:1304.0004 [pdf] submitted on 2013-04-02 01:26:20

Resolving the Decision Version of the Directed Hamiltonian Path (Cycle) Problem Under Two Special Conditions by Method of Matrix Determinant: an Overview

Authors: Okunoye Babatunde O.
Comments: 6 Pages.

In computational complexity, the Decision version of the Directed Hamiltonian Path Problem is known to be NP-complete (Nondeterministic-Polynomial complete). There are no known efficient algorithms for its resolution in Polynomial time. In three papers, the author shows that this problem can be resolved in Polynomial time under two special conditions relating to the determinant of a matrix: the absence of zero rows (columns) and similar rows (columns). In this paper, the author gives a brief overview of the proposed solution and the P vs NP problem.
Category: Combinatorics and Graph Theory

[1] viXra:1304.0002 [pdf] replaced on 2013-04-11 15:24:12

Polynomial Algorithms for Shortest Hamiltonian Path and Circuit

Authors: Dhananjay P. Mehendale
Comments: 14 Pages

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.
Category: Combinatorics and Graph Theory