×
Booth, Kellogg S.; Lueker, George S.

Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. (English) Zbl 0367.68034

J. Comput. Syst. Sci. 13, 335-379 (1976).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0367.68034

Cited in 13 Reviews
Cited in 484 Documents

MSC:

68W99 Algorithms in computer science
68N01 General topics in the theory of software
05C05 Trees
PDF BibTeX XML Cite
\textit{K. S. Booth} and \textit{G. S. Lueker}, J. Comput. Syst. Sci. 13, 335--379 (1976; Zbl 0367.68034)
Full Text: DOI

References:

[1] Aho, A. V.; HOpcroft, J. E.; Ullman, J. D., (The Design And Analysis Of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, Mass.) · Zbl 0326.68005
[2] Benzer, S., On the topology of the genetic fine structure, Proc. Nat. Acad. Sci. U.S.A., 45, 1607-1620 (1959)
[3] Booth, K. S., PQ-tree algorithms, (Ph. D. Dissertation (1975), Department of Electrical Engineering and Computer Sciences, University of California: Department of Electrical Engineering and Computer Sciences, University of California Berkeley, California), (Also available as UCRL-51953 from Lawrence Livermore Laboratory, Livermore, California, 1975)
[4] Coffman, E. G.; Graham, R. L., Optimal scheduling for two-processor systems, Acta Informatica, 1, 200-213 (1972) · Zbl 0248.68023
[5] Dirac, G. A., On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg, 25, 71-76 (1961) · Zbl 0098.14703
[8] Fulkerson, D. R.; Gross, O. A., Incidence matrices and interval graphs, Pacific J. Math., 15, 835-855 (1965) · Zbl 0132.21001
[9] Gavril, F., An algorithm for testing chordality of graphs, Inform. Proc. Lett., 3, No. 4, 110-112 (1975) · Zbl 0304.05122
[10] Ghosh, S. P., File organization: the consecutive retrieval property, Comm. ACM, 9, 802-808 (1972) · Zbl 0246.68004
[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] Hirschberg, D.; Edelberg, M., On the complexity of computing graph isomorphism, (Technical Report TR-130 (August 1973), Princeton University, Computer Science Laboratory, Department of Electrical Engineering, Princeton University: Princeton University, Computer Science Laboratory, Department of Electrical Engineering, Princeton University Princeton, N.J.)
[13] Hajós, G., Über eine art von graphen, Internationale Mathematische Nachrichten, 11, 65 (1957)
[14] Hopcroft, J. E.; Tarjan, R. E., Efficient planarity testing, J. ACM, 21, 549-568 (1974) · Zbl 0307.68025
[15] Jennings, G., Representation of a collection of finite sets as intervals on a line (1974), Courant Institute, New York University, manuscript
[16] Kendall, D. G., Incidence matrices, interval graphs and seriation in archaeology, Pacific J. Math., 28, No. 3, 565-570 (1969) · Zbl 0185.03301
[17] Kuratowski, K., Sur le problème des courbes gauches en topologie, Fund. Math., 15, 271-283 (1930) · JFM 56.1141.03
[19] Lekkerkerker, C. G.; Boland, J. Ch., Representation of a finite graph by a set of intervals on the real line, Fund. Math., 51, 45-64 (1962) · Zbl 0105.17501
[20] Lempel, A.; Even, S.; Cederbaum, I., An algorithm for planarity testing of graphs, (Rosenstiehl, P., Theory of Graphs: International Symposium. Theory of Graphs: International Symposium, Rome, July, 1966 (1967), Gordon and Breach: Gordon and Breach New York), 215-232 · Zbl 0197.50204
[21] Lueker, G. S., Efficient algorithms for chordal graphs and interval graphs, (Ph. D. Dissertation (1975), Program in Applied Mathematics and the Department of Electrical Engineering, Princeton University: Program in Applied Mathematics and the Department of Electrical Engineering, Princeton University Princeton, N.J.)
[23] Rose, D., Triangulated graphs and the elimination process, J. Math. Anal. Appl., 32, 597-609 (1970) · Zbl 0216.02602
[24] Rose, D. J.; Tarjan, R. E.; Lueker, G. S., Algorithmic aspects of vertex elimination on graphs, SIAM J. Computing, 5, No. 2, 266-283 (June 1976)
[25] Ryser, H. J., Combinatorial configurations, SIAM J. Appl. Math., 17, No. 3, 593-602 (May 1969)
[26] Sethi, R., Scheduling graphs on two processors, SIAM J. Computing, 5, No. 1, 73-82 (March 1976)
[27] Stoffers, K. E., Scheduling of traffic lights—a new approach, Transportation Research, 2, 199-234 (1968)
[28] Strassen, V., Gaussian elimination is not optimal, Numer. Math., 13, 354-356 (1969) · Zbl 0185.40101
[30] Tucker, A. C., Matrix characterizations of circular-arc graphs, Pacific J. Math., 39, No. 2, 535-545 (1971) · Zbl 0226.05125
[31] Tucker, A. C., A structure theorem for the consecutive 1’s property, J. Combinatorial Theory, 12(B), 153-162 (1972) · Zbl 0208.52402
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.