Paths in interval graphs and circular arc graphs
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?
scientific article; zbMATH DE number 179588
scientific article