×
Syslo, M. M.; Dzikiewicz, J.

Computational experiences with some transitive closure algorithms. (English) Zbl 0336.05003

Computing 15, 33-39 (1975).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0336.05003

Cited in 4 Documents

MSC:

05-04 Software, source code, etc. for problems pertaining to combinatorics
05C20 Directed graphs (digraphs), tournaments
68W99 Algorithms in computer science
Cite Review PDF
Full Text: DOI

References:

[1] Aho, A. V., Garey, M. R., Ullman, J. D.: The transitive reduction of directed graph. SIAM J. Comput.1, 131–137 (1972). · Zbl 0247.05128 · doi:10.1137/0201008
[2] Arlazarow, V. L., Dinic, E. A. Kronrod, M. A., Faradzehev, I. A.: On economical construction of the transitive closure of an oriented graph. DAN SSSR194, 487–488 (1970).
[3] Dzikiewicz, J.: Transitive closure algorithms. M.S. Dissertation, Dept. of Numerical Methods, University of Wroclaw, Wroclaw 1974. · Zbl 0336.05003
[4] Dzikiewicz, J.: An algorithm for finding the transitive closure of a digraph. Computing15, 75–79 (1975). · Zbl 0325.05103 · doi:10.1007/BF02252839
[5] Faradzehev, I. A.: Effective algorithms for solving some problems of directed graph theory. Ž. Vyčisl. Mat. i Mat. Fiz.10, 1049–1054 (1970).
[6] Fischer, M. J., Meyer, A. R.: Boolean matrix multiplication and transitive closure. IEEE Conf. Record of the Twelfth Annual Symp. on Switching and Automata Theory1971, 129–131.
[7] Floyd, R. W.: Algorithm 96: Ancestor. Comm. ACM5, 344 (1962). · doi:10.1145/367766.368166
[8] Furman, M. E.: Application of a method of fast multiplication of matrices in the problem of finding the transitive closure of a graph. DAN SSSR194, 524 (1970). · Zbl 0214.23602
[9] Harary, F., Norman, R. Z., Cartwright, D.: Structural models: An introduction to the theory of directed graphs. New York: Wiley. 1965. · Zbl 0139.41503
[10] Martynjuk, V. V.: On economical construction of the transitive closure of a binary relation. Ž. Vyčisl. Mat. i Mat. Fiz.2, 723–725 (1962).
[11] Munro, J. I.: Efficient determination of the transitive closure of a directed graph. Information Processing Letters1, 56–58 (1971). · Zbl 0221.68030 · doi:10.1016/0020-0190(71)90006-8
[12] O’Neil, P. E., O’Neil, E. J.: A fast expected time algorithm for Boolean matrix multiplication and transitive closure. Information and Control22, 132–138 (1973). · Zbl 0256.65016 · doi:10.1016/S0019-9958(73)90228-3
[13] Purdom, P.: A transitive closure algorithm. BIT10, 76–94 (1970). · Zbl 0193.14604 · doi:10.1007/BF01940892
[14] Sysło, M. M.: Transitive closure of a graph. Zastosow. Matem.14, 477–480 (1974). · Zbl 0296.05127
[15] Tarjan, R. E.: Depth, first search and linear graph algorithms. SIAM J. Comput.1, 146–160 (1972). · Zbl 0251.05107 · doi:10.1137/0201010
[16] Thorelli, L. E.: An algorithm for computing all paths in a graph. BIT6, 347–349 (1966). · Zbl 0144.45503 · doi:10.1007/BF01966095
[17] Warshall, S.: A theorem on Boolean matrices. Journ. ACM9, 11–12 (1962). · Zbl 0118.33104 · doi:10.1145/321105.321107
[18] Yen, J. Y.: Algorithms for finding all connectivities in directed and undirected networks. Preprint, 1973.
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.