The Complexity of HCP in Digraps with Degree Bound Two

Details The Complexity of HCP in Digraps with Degree Bound Two The Complexity of HCP in Digraps with Degree Bound Two

2007-04-03

arxiv.org/abs/0704.0309v3

Computer Science

Computational Complexity

10 pages, 4 figures, had been submitted to a Journal

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The Complexity of HCP in Digraps with Degree Bound Two does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Complexity of HCP in Digraps with Degree Bound Two, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of HCP in Digraps with Degree Bound Two will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-255641