Linear algorithms to recognize interval graphs and test for the consecutive ones property

ABSTRACT

A matrix of zeroes and ones is said to have the consecutive ones property if there is a permutation of its rows such that the ones in each column appear consecutively. This paper develops a data structure which may be used to test a matrix for the consecutive ones property, and produce the desired permutation of the rows, in linear time. One application of the consecutive ones property is in recognizing interval graphs. A graph is an interval graph if there exists a 1-1 correspondence between its vertices and a set of intervals on the real line such that two vertices are adjacent if and only if the corresponding intervals have a nonempty intersection. Fulkerson and Gross have characterized interval graphs as those for which the clique versus vertex incidence matrix has the consecutive ones property. In testing this particular matrix for the consecutive ones property we may process the columns in a special order to simplify the algorithm. This yields the interval graph recognition algorithm which is presented in section 2; section 3 indicates how this algorithm may be extended to the general consecutive ones problem.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Benzer, S., "On the Topology of the Genetic Fine Structure," Proc. Nat. Acad. Sci. U.S.A., 45 (1959), pp. 1607-1620.
• 3: Booth, K.S., and Tarjan, R.E., "Layered Breadth-First Search and Chordal Graphs," draft.
• 4: Cohen, J., "Interval Graphs and Food Webs," The RAND Corporation, D-17696-PR.
• 5: Coffman, E.G., Jr., and Graham, R.L., "Optimal Scheduling for Two-Process-or Systems," Acta Informatica, 1 (1972), pp. 200-213.
• 6: Even, S., private communication to R. Tarjan.
• 7: Fulkerson, D.R., and Gross, O.A., "Incidence Matrices and Interval Graphs," Pac. J. Math., 15 (1965), pp. 835-855.
• 8: Ghosh, S.P., "On the Theory of Consecutive Storage of Relevant Records," Information Sciences, 6 (1973), pp. 1-9.
• 9: Gilmore, P.C., and Hoffman, A.J., "A Characterization of Comparability Graphs and of Interval Graphs," Can. J. Math., 16 (1964), pp. 539-548.
• 10: Hajos, G., "Über eine Art von Graphen," Internationale Math. Nachrichten, 11 (1957), p. 65.
• 11: John Hopcroft , Robert Tarjan, Efficient Planarity Testing, Journal of the ACM (JACM), v.21 n.4, p.549-568, Oct. 1974 [doi>10.1145/321850.321852]
• 12: Karp, R.M., "Reducibility among Combinatorial Problems," in Complexity of Computer Computations, R. E. Miller and J.W. Thatcher, eds., Plenum Press, New York, 1972, pp. 85-103.
• 13: Kendall, D.G., "Some Problems and Methods in Statistical Archaeology," World Archaeology, 1 (1969), pp. 68-76.
• 14: Lueker, G.S., "Structured Breadth First Search and Chordal Graphs," Technical Report 158, Dept. of Elec. Eng., Computer Science Lab., Princeton University, August 1974.
• 15: Lekkerkerker, C.G., and Boland, J. Ch., "Representation of a Finite Graph by a Set of Intervals on the Real Line," Fund. Math., 51 (1962), pp. 45-64.
• 16: Lempel, A., Even, S., and Cederbaum, I., "An Algorithm for Planarity Testing of Graphs," Theory of Graphs: International Symposium: Rome, July, 1966, P. Rosenstiehl, ed., Gordon and Breach, New York, 1967, pp. 215-232.
• 17: Pnueli, A., Lempel, A., and Even, S., "Transitive Orientation of Graphs and Identification of Permutation Graphs," Can. J. Math., 23 (1971), pp. 160-175.
• 18: Roberts, F.S., Discrete Mathematical Models, with Applications to Social, Biological and Environmental Problems, Prentice-Hall, Englewood Cliffs, N.J., to appear.
• 19: Roberts, F.S., Representations of Indifference Relations, Ph.D. Thesis, Stanford University, 1968.
• 20: Roberts, F.S., "Indifference Graphs," in Proof Techniques in Graph Theory, F. Harary, ed., Academic Press, New York, 1969, pp. 139-146.
• 21: Rose, D.J., Tarjan, R.E., and Lueker, G.S., "Algorithmic Aspects of Vertex Elimination on Graphs," draft.
• 22: Sethi, R., "Algorithms for Nonpreemptive Scheduling on Two Processors," Computer Science Department, Pennsylvania State University, unpublished manuscript, 1974.
• 23: Stoffers, K.E., "Scheduling of Traffic Lights—a New Approach," Transportation Research, 2 (1968), pp. 199-234.
• 24: Tarjan, R.E., "Implementation of an Efficient Algorithm for Planarity Testing of Graphs," Dec. 1969, unpublished manuscript.
• 25: Tucker, A., "Matrix Characterizations of Circular-Arc Graphs," Pac. J. Math., 39 (1971), pp. 535-545.
• 26: Tucker, A., "A Structure Theorem for the Consecutive 1's Property," J. Comb. Theory, 12(B) (1972), pp. 153-162.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES

General Terms:
Algorithms, Theory