Statements (19)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
Graph theory concept
|
| gptkbp:abbreviation |
DHP
|
| gptkbp:application |
gptkb:Computational_biology
Scheduling Routing |
| gptkbp:complexity |
NP-complete
|
| gptkbp:decision |
Does a given directed graph have a Hamiltonian path?
|
| gptkbp:defines |
A path in a directed graph that visits each vertex exactly once
|
| gptkbp:field |
gptkb:Graph_theory
Discrete mathematics |
| https://www.w3.org/2000/01/rdf-schema#label |
Directed Hamiltonian Path
|
| gptkbp:isSolvable |
Exponential time (in general case)
|
| gptkbp:namedAfter |
gptkb:William_Rowan_Hamilton
|
| gptkbp:relatedTo |
gptkb:Hamiltonian_cycle
gptkb:Hamiltonian_path gptkb:Traveling_salesman_problem Directed graph |
| gptkbp:bfsParent |
gptkb:Reducibility_Among_Combinatorial_Problems_(Karp,_1972)
|
| gptkbp:bfsLayer |
6
|