diophantus

Log in | Create account
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

Zhu Guohun
02 Apr 2007 cs.CC, cs.DM arxiv.org/abs/0704.0309
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

There are no comments yet.

Log in to leave a comment.


Reviews

There are no reviews yet.

Log in to leave a review.