Algebraic structures for transitive closure. (English) Zbl 0358.68061


68W99 Algorithms in computer science
05C35 Extremal problems in graph theory
15B33 Matrices over special rings (quaternions, finite fields, etc.)


Algorithm 97
Full Text: DOI Link


[1] Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D., The Design and Analysis of Computer Algorithms, ((1974), Addison-Wesley: Addison-Wesley Reading, MA), 195-201 · Zbl 0326.68005
[2] Backhouse, R. C.; Carré, B. A., Regular algebra applied to path-finding problems, J. Inst. Math. Appl., 15, 161-186 (1975) · Zbl 0304.68082
[3] Conway, J. H., Regular Algebra and Finite Machines, ((1971), Chapman and Hall: Chapman and Hall London), 109-111 · Zbl 0231.94041
[4] Dijkstra, E. W., A note on two problems in connection with graphs, Numer. Math., 1, 269-271 (1959) · Zbl 0092.16002
[5] Floyd, R. W., Algorithm 97: shortest path, Comm. ACM, 5, 6, 345 (1962)
[6] Gondran, M., Algèbre linéaire et Cheminement dans un graphe, R.A.I.R.O., 9, 77-99 (1975) · Zbl 0311.90071
[7] Kam, John B.; Ullman, Jeffrey D., Global data flow analysis and iterative algorithms, J. ACM, 23, 1, 158-171 (1976) · Zbl 0315.68031
[8] Kleene, S. C., Representation of events in nerve nets and finite automata, (Shannon, C. E.; McCarthy, J., Automata Studies (1956), Princeton University Press: Princeton University Press Princeton NJ), 3-42
[9] Lehmann, Daniel J., Algebraic structures for transitive closure, (Theory of Computation Report No. 10 (1976), Department of Computer Science, The University of Warwick) · Zbl 0358.68061
[10] Roy, B., Transitivité et connexité, C.R. Acad. Sci., 249, 216 (1959) · Zbl 0092.15902
[11] Tarjan, R. E., Solving path problems on directed graphs, (Technical Report (1975), Stanford Computer Science Department)
[13] Warshall, S., A theorem on Boolean matrices, J. ACM, 9, 1, 11-12 (1962) · Zbl 0118.33104
[14] Yoeli, M., A note on a generalisation of boolean matrix theory, Amer. Math. Monthly, 68, 552-557 (1961) · Zbl 0115.02103
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.