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; zbMATH DE number 4123306
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A note on the Hamiltonian circuit problem on directed path graphs |
scientific article; zbMATH DE number 4123306 |
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
0.9073597
0 references
0.90639955
0 references
0.90521705
0 references
0.9050137
0 references
0.90447426
0 references
0.90414214
0 references
0.8993529
0 references
0.89901924
0 references
