A note on the Hamiltonian circuit problem on directed path graphs (Q1262132)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A note on the Hamiltonian circuit problem on directed path graphs |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A note on the Hamiltonian circuit problem on directed path graphs |
scientific article |
Statements
A note on the Hamiltonian circuit problem on directed path graphs (English)
0 references
1989
0 references
The problem of finding a Hamiltonian circuit (HCP) is a well-known NP- complete problem for general graphs. It is also known to be NP-complete for several special classes of graphs. The author shows that HCP is NP- complete for directed path graphs by using a characterization of these graphs in terms of their cliques [\textit{C. L. Monma} and \textit{V. K. Wei}, J. Comb. Theory, Ser. B 41, 141-181 (1986; Zbl 0572.05049)].
0 references
Hamiltonian circuit
0 references
NP-complete
0 references
directed path graphs
0 references
cliques
0 references
0 references
