Paths in interval graphs and circular arc graphs (Q1210553)
From MaRDI portal
!
WARNING
This is the item page for this Wikibase entity, intended for internal use and editing purposes.
Please use the normal view instead:
scientific article; zbMATH DE number 179588
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Paths in interval graphs and circular arc graphs |
scientific article; zbMATH DE number 179588 |
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
0 references
0.9289887
0 references
0.92256624
0 references
0 references
0 references
0.9136256
0 references
0 references
0 references
0.89830697
0 references
