Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm (Q1198484)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm |
scientific article |
Statements
Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm (English)
0 references
16 January 1993
0 references
The cocomparability graph of a partial order is the graph whose edges are the incomparable pairs in the partial order. It is shown that the Hamiltonian Path problem can be solved in polynomial time for cocomparability graphs, and thus for the subclass of permutation graphs. The proof uses results on the bump numbers of partially ordered sets, and relationships between Hamiltonian paths in the cocomparability graphs and the bump numbers. The existence of polynomial time algorithms for path (cycle) completion problems in cocomparability graphs is proved.
0 references
bump number algorithm
0 references
cycle
0 references
cocomparability graph
0 references
partial order
0 references
Hamiltonian Path problem
0 references
permutation graphs
0 references
path
0 references