# zbMATH — the first resource for mathematics

Paths in interval graphs and circular arc graphs. (English) Zbl 0777.05081
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?

##### MSC:
 05C45 Eulerian and Hamiltonian graphs 05C85 Graph algorithms (graph-theoretic aspects) 05C38 Paths and cycles
Full Text:
##### References:
  Apostolico, A.; Hambrusch, S.E., Finding maximum cliques in circular-arc graphs, Inform. process. lett., 26, 209-215, (1987/88) · Zbl 0654.68082  Bertossi, A.A., Finding Hamiltonian circuits in proper interval graphs, Inform. process. lett., 17, 97-101, (1983) · Zbl 0512.68046  Bertossi, A.A.; Bonuccelli, M.A., Hamiltonian circuits in interval graph generalizations, Inform. process. lett., 23, 195-200, (1986) · Zbl 0627.68056  Bodlaender, H.L., ACHROMATIC NUMBER is NP-complete for cographs and interval graphs, () · Zbl 0684.68046  Bonuccelli, M.A., Dominating sets and domatic number of circular arc graphs, Discrete appl. math., 12, 203-213, (1985) · Zbl 0579.05051  Booth, K.S.; Lueker, G.S., Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms, J. comput. systems sci., 13, 335-379, (1976) · Zbl 0367.68034  Damaschke, P., Zur kompliziertheit von hamiltonschen problemen in speziellen graphenklassen, ()  Damaschke, P., The Hamiltonian circuit problem for circle graphs is NP-complete, Inform. process. lett., 32, 1-2, (1989) · Zbl 0681.68062  P. Damaschke and H. Müller, Hamiltonian circuits in convex and chordal bipartite graphs, manuscript. · Zbl 0706.68055  Garey, M.R.; Johnson, D.S., Computers and intractability, a guide to the theory of NP-completeness, (1979), Freeman San Francisco · Zbl 0411.68039  Gilmore, P.C.; Hoffman, A.J., A characterization of comparability graphs and of interval graphs, Canad. J. math., 16, 539-548, (1964) · Zbl 0121.26003  Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054  Golumbic, M.C., Interval graphs and related topics, Discrete math., 55, 113-121, (1985) · Zbl 0568.05046  Johnson, D.S., The NP-completeness column: an ongoing guide, J. algorithms, 6, 434-451, (1985) · Zbl 0608.68032  Keil, J.M., Finding Hamiltonian circuits in interval graphs, Inform. process. lett., 20, 201-206, (1985) · Zbl 0578.68053  J.M. Keil and D. Schaefer, An optimal algorithm for finding dominating cycles in circular-arc graphs, Preprint, Dept. of Comput. Sci., Univ. of Sascatchewan, Sascatoon, Canada. · Zbl 0753.05063
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.