A Note on the Hamiltonian Circuit Problem on Directed Path Graphs

Simple item page
dc.contributor.authorNarasimhan, Girien_US
dc.date.accessioned2012-03-15T16:50:05Z
dc.date.available2012-03-15T16:50:05Z
dc.date.created1989en_US
dc.date.issued1989
dc.description.abstractBertossi and Bonuccelli [2] proved that the Hamiltonian Circuit problem in NP-Complete even when the inputs are restricted to the special class of Undirected Path graphs. The corresponding problem on Directed Path graphs was left as an open problem. We use a characterization of Directed Path graphs due to Monma and Wei [8] to prove that the Hamiltonian Circuit problem and the Hamiltonian Path problem are NP-Complete on Directed Path graphs.en_US
dc.format.mimetypeapplication/pdfen_US
dc.identifier.citationTR839
dc.identifier.urihttp://digital.library.wisc.edu/1793/59108
dc.publisherUniversity of Wisconsin-Madison Department of Computer Sciencesen_US
dc.titleA Note on the Hamiltonian Circuit Problem on Directed Path Graphsen_US
dc.typeTechnical Reporten_US

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
TR839.pdf
Size:
487.97 KB
Format:
Adobe Portable Document Format
Download

Collections

CS Technical Reports