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?

05C45 Eulerian and Hamiltonian graphs
05C85 Graph algorithms (graph-theoretic aspects)
05C38 Paths and cycles
Full Text: DOI
[1] Apostolico, A.; Hambrusch, S.E., Finding maximum cliques in circular-arc graphs, Inform. process. lett., 26, 209-215, (1987/88) · Zbl 0654.68082
[2] Bertossi, A.A., Finding Hamiltonian circuits in proper interval graphs, Inform. process. lett., 17, 97-101, (1983) · Zbl 0512.68046
[3] Bertossi, A.A.; Bonuccelli, M.A., Hamiltonian circuits in interval graph generalizations, Inform. process. lett., 23, 195-200, (1986) · Zbl 0627.68056
[4] Bodlaender, H.L., ACHROMATIC NUMBER is NP-complete for cographs and interval graphs, () · Zbl 0684.68046
[5] Bonuccelli, M.A., Dominating sets and domatic number of circular arc graphs, Discrete appl. math., 12, 203-213, (1985) · Zbl 0579.05051
[6] 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
[7] Damaschke, P., Zur kompliziertheit von hamiltonschen problemen in speziellen graphenklassen, ()
[8] Damaschke, P., The Hamiltonian circuit problem for circle graphs is NP-complete, Inform. process. lett., 32, 1-2, (1989) · Zbl 0681.68062
[9] P. Damaschke and H. Müller, Hamiltonian circuits in convex and chordal bipartite graphs, manuscript. · Zbl 0706.68055
[10] Garey, M.R.; Johnson, D.S., Computers and intractability, a guide to the theory of NP-completeness, (1979), Freeman San Francisco · Zbl 0411.68039
[11] 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
[12] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054
[13] Golumbic, M.C., Interval graphs and related topics, Discrete math., 55, 113-121, (1985) · Zbl 0568.05046
[14] Johnson, D.S., The NP-completeness column: an ongoing guide, J. algorithms, 6, 434-451, (1985) · Zbl 0608.68032
[15] Keil, J.M., Finding Hamiltonian circuits in interval graphs, Inform. process. lett., 20, 201-206, (1985) · Zbl 0578.68053
[16] 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.