Finding Hamiltonian circuits in interval graphs. (English) Zbl 0578.68053
The problem of deciding whether a graph has a Hamiltonian circuit has been shown NP-complete on many restricted classes of graphs. This paper adds to the classes of graphs for which a polynomial time algorithm for the Hamiltonian circuit problem is known. A linear time algorithm for the problem in interval graphs is developed.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C45 | Eulerian and Hamiltonian graphs |
| 05C38 | Paths and cycles |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Bertossi, A. A., The edge Hamiltonian path problem is NP-complete, Inform. Process. Lett., 13, 157-159 (1981) · Zbl 0495.68058 |
| [2] | Bertossi, A. A., Finding Hamiltonian circuits in proper interval graphs, Inform. Process. Lett., 17, 97-101 (1983) · Zbl 0512.68046 |
| [3] | Booth, K. S.; Leuker, G. S., Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms, J. Comput. System Sci., 13, 335-379 (1976) · Zbl 0367.68034 |
| [4] | Fulkerson, D. R.; Gross, O. A., Incidence matrices with the consecutive ones property, Bull. Amer. Math. Soc., 70, 681-684 (1964) · Zbl 0126.39501 |
| [5] | Garey, M. R.; Johnson, D. S., (Computers and Intractability, A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco) · Zbl 0411.68039 |
| [6] | Garey, M. R.; Johnson, D. S.; Tarjan, R. E., The planar Hamiltonian circuit problem is NP-complete, SIAM J. Comput., 5, 704-714 (1976) · Zbl 0346.05110 |
| [7] | 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 |
| [8] | Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054 |
| [9] | Gouyou-Beauchamps, D., The Hamiltonian circuit problem is polynomial for 4-connected planar graphs, SIAM J. Comput., 11, 3, 529-539 (1982) · Zbl 0486.68061 |
| [10] | Itai, A.; Papadimitriou, C. H.; Szwarcfiter, J. L., Hamiltonian paths in grid graphs, SIAM J. Comput., 11, 4, 676-686 (1982) · Zbl 0506.05043 |
| [11] | Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York), 85-103 · Zbl 0366.68041 |
| [12] | Krishnamoorthy, M. S., An NP-hard problem in bipartite graphs, SIGACT News, 7, 1, 26 (1976) |
| [13] | Lekkerkerker, C. G.; Boland, J. Ch., Representation of a finite graph by a set of intervals on the real line, Fundamenta Mathematicae, 51, 45-64 (1962) · Zbl 0105.17501 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
