Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Aho, 1974

Benzer, 1959, On the topology of the genetic fine structure, Proc. Nat. Acad. Sci. U.S.A., 45, 1607, 10.1073/pnas.45.11.1607

Booth, 1975, PQ-tree algorithms

Coffman, 1972, Optimal scheduling for two-processor systems, Acta Informatica, 1, 200, 10.1007/BF00288685

Dirac, 1961, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg, 25, 71, 10.1007/BF02992776

S. Even, personal communication.

S. Even and R. E. Tarjan, Computing an st-numbering, Theoretical Computer Science, to appear.

Fulkerson, 1965, Incidence matrices and interval graphs, Pacific J. Math., 15, 835, 10.2140/pjm.1965.15.835

Gavril, 1975, An algorithm for testing chordality of graphs, Inform. Proc. Lett., 3, 110, 10.1016/0020-0190(75)90043-5

Ghosh, 1972, File organization: the consecutive retrieval property, Comm. ACM, 9, 802, 10.1145/361573.361578

Gilmore, 1964, A characterization of comparability graphs and of interval graphs, Canad. J. Math., 16, 539, 10.4153/CJM-1964-055-5

Hirschberg, 1973, On the complexity of computing graph isomorphism

Hajós, 1957, Über eine art von graphen, Internationale Mathematische Nachrichten, 11, 65

Hopcroft, 1974, Efficient planarity testing, J. ACM, 21, 549, 10.1145/321850.321852

Jennings, 1974

Kendall, 1969, Incidence matrices, interval graphs and seriation in archaeology, Pacific J. Math., 28, 565, 10.2140/pjm.1969.28.565

Kuratowski, 1930, Sur le problème des courbes gauches en topologie, Fund. Math., 15, 271, 10.4064/fm-15-1-271-283

R. E. Ladner, M. J. Fischer, and S. Young, private communication.

Lekkerkerker, 1962, Representation of a finite graph by a set of intervals on the real line, Fund. Math., 51, 45, 10.4064/fm-51-1-45-64

Lempel, 1967, An algorithm for planarity testing of graphs, 215

Lueker, 1975, Efficient algorithms for chordal graphs and interval graphs

F. S. Roberts, “Discrete Mathematical Models, with Applications to Social, Biological, and Environmental Problems” Prentice-Hall, Englewood Cliffs, N.J., to appear.

Rose, 1970, Triangulated graphs and the elimination process, J. Math. Anal. Appl., 32, 597, 10.1016/0022-247X(70)90282-9

Rose, 1976, Algorithmic aspects of vertex elimination on graphs, SIAM J. Computing, 5, 266, 10.1137/0205021

Ryser, 1969, Combinatorial configurations, SIAM J. Appl. Math., 17, 593, 10.1137/0117056

Sethi, 1976, Scheduling graphs on two processors, SIAM J. Computing, 5, 73, 10.1137/0205005

Stoffers, 1968, Scheduling of traffic lights—a new approach, Transportation Research, 2, 199, 10.1016/0041-1647(68)90016-6

Strassen, 1969, Gaussian elimination is not optimal, Numer. Math., 13, 354, 10.1007/BF02165411

R. E. Tarjan, personal communication.

Tucker, 1971, Matrix characterizations of circular-arc graphs, Pacific J. Math., 39, 535, 10.2140/pjm.1971.39.535

Tucker, 1972, A structure theorem for the consecutive 1's property, J. Combinatorial Theory, 12(B), 153, 10.1016/0095-8956(72)90019-6