Paths in interval graphs and circular arc graphs (Q1210553): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:32, 5 March 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