Paths in interval graphs and circular arc graphs (Q1210553): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
| links / mardi / name | links / mardi / name | ||
Revision as of 07:22, 31 January 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Paths in interval graphs and circular arc graphs |
scientific article |
Statements
Paths in interval graphs and circular arc graphs (English)
0 references
30 August 1993
0 references
Interval graphs and circular arc graphs are intersection graphs of intervals on a line resp. of arcs on a circle. We give polynomial-time algorithms for several path cover problems in such graphs, e.g. for finding a Hamiltonian path in a circular arc graph. Some seemingly similar problems remain open here: Can one find in polynomial time (1) a Hamiltonian cycle in a circular arc graph, (2) a Hamiltonian path with prescribed start vertex in an interval graph?
0 references
circular arc graphs
0 references
intersection graphs
0 references
polynomial-time algorithms
0 references
Hamiltonian path
0 references
