A New Method of Checking the Consistency of Precedence Matrices

ABSTRACT

A new method of checking the consistency of precedence matrices is demonstrated. The method is based on the theorem that a precedence matrix is consistent if and only if every principal submatrix has at least one zero row or zero column. Because this method recognizes inconsistencies in their implicit form whereas the conventional method recognized only explicit contradictions, a considerable saving in time and effort can be effected, since the process of making explicit all the implications of a precedence matrix particularly a larger one, is a tedious time-consuming operation.

REFERENCES

• 1: EDW.~RD W. BAP~_~KIN, Precedence m~trices, University of California ~Ianagement Sciences Research Project, Research Report No. 26, Dccembcr, 1953.
• 2: A L. LI~INER, W. A. NOTZ, J. L. SMITH, AND 2~k. WEINBERG~R, Organizing a negwork of computers to meet deadlines, Proceedings of the Eastern Joint Computer Conference, December 9-13, 1957, Washington, D. C., pp 115-128

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

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

General Terms:
Measurement, Performance, Reliability, Theory