NP-Completeness of Hamiltonian Cycle Problem on Rooted Directed Path Graphs

Details NP-Completeness of Hamiltonian Cycle Problem on Rooted Directed Path Graphs NP-Completeness of Hamiltonian Cycle Problem on Rooted Directed Path Graphs

2008-09-15

arxiv.org/abs/0809.2443v1

Computer Science

Discrete Mathematics

Scientific paper

The Hamiltonian cycle problem is to decide whether a given graph has a Hamiltonian cycle. Bertossi and Bonuccelli (1986, Information Processing Letters, 23, 195-200) proved that the Hamiltonian Cycle Problem is NP-Complete even for undirected path graphs and left the Hamiltonian cycle problem open for directed path graphs. Narasimhan (1989, Information Processing Letters, 32, 167-170) proved that the Hamiltonian Cycle Problem is NP-Complete even for directed path graphs and left the Hamiltonian cycle problem open for rooted directed path graphs. In this paper we resolve this open problem by proving that the Hamiltonian Cycle Problem is also NP-Complete for rooted directed path graphs.

Affiliated with

Also associated with

No associations

Rating

NP-Completeness of Hamiltonian Cycle Problem on Rooted Directed Path Graphs 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 NP-Completeness of Hamiltonian Cycle Problem on Rooted Directed Path Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and NP-Completeness of Hamiltonian Cycle Problem on Rooted Directed Path Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-634420