Methods for Checking the Consistency of Precedence Constraints

References

• Aho , A. V. , Garey , M. R. and Ullman , J. D. , “ The Transitive Reduction of a Directed Graph ,” SIAM J. Comput. 12 , 131 – 37 , ( 1962 ).
   Google Scholar
• Aho , A. V. , Hopcioft , J. E. and Ullman , J. D. , The Design and Analysis of Computer Algorithms , Addison-Wesley ( 1974 ) .
   Google Scholar
• Backhouse , R. C. and Carré , B. A. , “ Regular Algebra Applied to Pathfinding Problems ,” J. Inst. Maths Applies , 15 , 161 – 86 , ( 1975 ).
   Google Scholar
• Barankin , E. W. , “ Precedence Matrices ,” Industrial Logistics Research Project No. 26, University of California , Los Angeles , (December 2, 1953 ) .
   Google Scholar
• Elmaghraby , S. E. , Activity Networks: Project Planning and Control by Network Models , Wiley ( 1977 ) .
   Google Scholar
• Elmaghraby , S. E. , Private communication ( 1978 ).
   Google Scholar
• Fox , B. L. and Landi , D. M. , “ An Algorithm for Identifying the Ergodic Subchains and Transient States of a Stochastic Matrix ,” Comm. ACM 11 9 , 619 – 621 ( 1968 ).
   Google Scholar
• Geller , D. P. and Harary , F. , “ Arrow Diagrams are Line Digraphs ,” SIAM J. Appl. Math. , 16 6 , 1141 – 1145 ( 1968 ).
   Google Scholar
• Harary , F. , “ Graph Theoretic Methods in the Management Sciences ,” Management Science , 5 , 387 – 403 ( 1959 ).
   Web of Science ®Google Scholar
• Harary , F. , “ On the Consistency of Precedence Matrices ,” Journal of the ACM , 7 , 255 – 259 ( 1960 ).
   Google Scholar
• Harary , F. , Norman , R. Z. and Cartwright , D. , Structural Models: An Introduction to the Theory of Directed Graphs , Wiley ( 1965 ) .
   Google Scholar
• Holt , R. C. and Reingold , E. M. ,“ On the Time Required to Detect Cycles and Connectivity in Graphs ,” Mathematical Systems Theory , 6 , 2 , 103 – 106 ( 1972 ).
   Google Scholar
• Karayiannis , A. and Loizou , G. , “ Cycle Detection in Critical Path Networks , Information Processing Letters , 7 1 , 15 – 19 , ( 1978 ).
   Google Scholar
• Karp , R. , Unpublished Lecture at the Summer School in Combinatorial Optimization, SOGESTA, Urbino , Italy , ( July 1978 ) .
   Google Scholar
• Knuth , D. E. , The Art of Computer Programming, Vol. 1: Fundamental Algorithms , Addison-Wesley ( 1968 ) .
   Google Scholar
• Lawler , E. L. , Combinatorial Optimization: Networks and Matrices , Holt , Rinehart and Winston ( 1976 ) .
   Google Scholar
• Lempel , A. and Cederbaum , I. , “ Minimum Feedback Arc and Vertex Sets of a Directed Graph ,” IEEE Trans on Circuit Theory , CT-13 4 , 399 – 402 ( 1966 ).
   Google Scholar
• Marimont , R. B. , “ A New Method of Checking the Consistency of Precedence Matrices ,” Journal of the ACM , 6 , 164 - 171 ( 1959 ).
   Google Scholar
• Moyles , D. M. and Thompson , G. L. , “ An Algorithm for Finding a Minimum Equivalent Graph of a Digraph ,” Journal of the ACM , 16 3 , 455 – 460 ( 1969 ).
   Google Scholar
• Munro , I. , “ Efficient Determination of the Transitive Closure of a Directed Graph ,” Information Processing Letters , 1 , 56 – 58 ( 1971 ).
   Google Scholar
• Nolfemeier , H. ,“ Reduktion von Präzendenzstrukturen ,” Zeit scrift für Operations Research , Band 20 , 151 – 159 ( 1976 ).
   Google Scholar
• Prosser , R. T. , “ Applications of Boolean Matrices to the Analysis of Flow Diagrams ,” Proc. Eastern Joint Computer Conference ( 1959 ).
   Google Scholar
• Purdom , P. Jr. , “ A Transitive Closure Algorithm ,” BIT 10 , 76 – 94 ( 1970 ).
   Google Scholar
• Reingold , E. M. , Nievergelt , J. and Deo , N. , Combinatorial Algorithms: Theory and Practice , Prentice-Hall ( 1977 ) .
   Google Scholar
• Richardson , M. , “ On Weakly Ordered Systems ,” Bulletin of the American Mathematical Society , 52 , 113 – 116 ( 1946 ).
   Web of Science ®Google Scholar
• Ross , I. C. and Harary , F. , “ A Description of Strengthening and Weakening Members of a Group ,” Sociometry , 22 , 139 – 147 ( 1959 ).
   Google Scholar
• Roy , M. B. , “ Transitivité et connexité Comptes Rendus Acad Set , Tome 249 , 216 – 218 ( 1959 ).
   Web of Science ®Google Scholar
• Sargent , R. W. H. and Westerberg , A. W. , “ 'Speed-up' in Chemical Engineering Design ,” Trans. Instn. Chem. Engrs , 42 , T190 - T197 ( 1964 ).
   Google Scholar
• Schnorr , C. P. , “ An Algorithm for Transitive Closure with Linear Expected Time ,” SIAM J. Comput. , 7 2 , 127 – 133 ( 1978 ).
   Google Scholar
• Smeds , P. A. , Strandh , R. , and Tellström , G. , “ Computational Experience of Algorithms for Finding the Strong Components of Almost Acyclic Digraphs ,” Report 2–1980-9, Dept. of Math., Linkoping Institute of Technology ( 1980 ) .
   Google Scholar
• Steward , D. V. , “ Partitioning and Tearing Systems of Equations ,” SIAM J. Numer. Anal Ser. B , 2 , 345 – 365 ( 1965 ).
   Google Scholar
• Tarjan , R. , “ Depth-first Search and Linear Graph Algorithms ,” SIAM J. Comput. , 1 2 , 146 – 160 ( 1972 ).
   Google Scholar
• Toth , P. , “ Finding a Minimal Equivalent Graph of a Digraph ,” Lecture at the School on Analysis and Design of Algorithms in Combinatorial Optimization, CISM , Udine , Italy ( Sept. 1979 ) .
   Google Scholar
• Warren , H. S. , “ A Modification of Warshall's Algorithm for the Transitive Closure of Binary Relations ,” Comm. ACM , 18 4 , 218 – 220 ( 1975 ).
   Google Scholar
• Warshall , S. , “ A Theorem on Boolean Matrices ,” Journal of the ACM , 91 , 11 – 12 ( 1962 ).
   Google Scholar