×

zbMATH — the first resource for mathematics

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

MSC:
68W99 Algorithms in computer science
68N01 General topics in the theory of software
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aho, A.V.; HOpcroft, J.E.; Ullman, J.D., ()
[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, (), (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
[6] {\scS. Even}, personal communication.
[7] {\scS. Even and R. E. Tarjan}, Computing an st-numbering, Theoretical Computer Science, to appear. · Zbl 0341.68029
[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, ()
[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
[18] {\scR. E. Ladner, M. J. Fischer, and S. Young}, private communication.
[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, (), 215-232 · Zbl 0197.50204
[21] Lueker, G.S., Efficient algorithms for chordal graphs and interval graphs, ()
[22] {\scF. S. Roberts}, “Discrete Mathematical Models, with Applications to Social, Biological, and Environmental Problems” Prentice-Hall, Englewood Cliffs, N.J., to appear. · Zbl 0363.90002
[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
[29] {\scR. E. Tarjan}, personal communication.
[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.