On the Consistency of Precedence Matrices

ABSTRACT

The consistency of precedence matrices is studied in the very natural geometric setting of the theory of directed graphs. An elegant recent procedure (Marimont [7]) for checking consistency is further justified by means of a graphical lemma. In addition, the “direction of future work” mentioned in [7] (to which the present communication may be regarded as a sequel) is developed here using graph theoretic methods. This is based on the relationship between the occurrence of directed cycles and the recognition of “strongly connected components” in a directed graph. An algorithm is included for finding these components in any directed graph. This is necessarily more complicated than determining whether there do not exist any directed cycles, i.e., whether or not a given precedence matrix is consistent.

REFERENCES

• 1: E. W. BARANKIN, Precedence matrices. University of California Management Sciences Research Project, Research Report No. 26, December, 1953.
• 2: F. HA~nY, A graph theoretic method for the complete reduction of a matrix with a view toward finding its eigenvalues. J. Math. Phys. 88 (1959), 104--111.
• 3: F. HAP~Rr, Graph theoretic methods in the management sciences. Management Science 5 (1959), 387-403.
• 4: F. HARARY, The number of functional digraphs. Math. Ann. 188 (1959), 203-211.
• 5: F. HARAnV AND Z. NORMAN, Graph theory as a mathematical model in social science. Ann Arbor, Institute for Social Research, 1953.
• 6: D. FK~NIO, Theorie der endlichen und uncndl~chen Graphen. Leipzig, 1936; reprinted New York, 1950.
• 7: Rosalind B. Marimont, A New Method of Checking the Consistency of Precedence Matrices, Journal of the ACM (JACM), v.6 n.2, p.164-171, April 1959 [doi>10.1145/320964.320973]
• 8: I. C. Ross ANY F. HARARY, A description of strengthening and weakening members of a group. Sociometry 22 (1959), 139-147.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Theory, Verification