Hello, this is beta version of diophantus. If you want to report about a mistake, please, write to
hello@diophantus.org
pdf
The Complexity of HCP in Digraps with Degree Bound Two
Abstract. The Hamiltonian cycle problem (HCP) in digraphs D with degree bound two is
solved by two mappings in this paper. The first bijection is between an
incidence matrix C_{nm} of simple digraph and an incidence matrix F of balanced
bipartite undirected graph G; The second mapping is from a perfect matching of
G to a cycle of D. It proves that the complexity of HCP in D is polynomial, and
finding a second non-isomorphism Hamiltonian cycle from a given Hamiltonian
digraph with degree bound two is also polynomial. Lastly it deduces P=NP base
on the results.
Reviews
There are no reviews yet.
Comments
Log in to leave a comment.
Reviews
There are no reviews yet.
Log in to leave a review.
There are no comments yet.