×

An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs. (English) Zbl 0592.68063

Summary: Computing the transitive closure of a directed graph can be reduced to determining the transitive closure of the (circuit-free) graph induced on the strongly connected components (the transitive closure of a strongly connected graph being the complete graph). A new algorithm is described to compute the transitive closure of a circuit-free graph, the complexity of which (in the worst-case sense) is better than O(MN) (M being the number of arcs and N the number of vertices). In the case of low density graphs, the resulting complexity is then better than that of previously known algorithms. In particular, for the class of low density circuitless graphs with vertices having in-degrees bounded by some fixed contant K, we show that our algorithm is linear in M’, the number of arcs in the transitive closure.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adleman, L.; Booth, K. S.; Preparata, F. P.; Ruzzo, W. L., Improved time and space bounds for boolean multiplication, Acta Informatica, 11, 61-199 (1978) · Zbl 0389.68016
[2] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms, ((1974), Addison-Wesley,: Addison-Wesley, Reading, MA), 195-199
[3] Arlazarov, U. L.; Dinic, E. A.; Kronrod, M. A.; Faradzev, I. A., On economical construction of the transitive closure of an oriented graph, Soviet Math. Dokl., 11, 5, 1209-1210 (1970) · Zbl 0214.23601
[4] Bloniarz, P. A.; Fischer, M. J.; Meyer, A. R., A note on the average time to compute transitive closure, (Michaelson, S.; Milner, R., Automata, Languages and Programming (1976), Edinburgh University Press), 425-434 · Zbl 0363.68055
[5] Booth, K. S., Boolean matrix multiplication using only \(O(n^{log7}\)(log \(n)\) bit operations, SIGACT News (1977)
[6] Coppersmith, D.; Winograd, S., On the asymptotic complexity of matrix multiplication, SIAM J. Comput., 11, 3, 472-492 (1982) · Zbl 0486.68030
[7] Dzikiewicz, J., An algorithm for finding the transitive closure of a relation, Comput., 15, 75-79 (1975) · Zbl 0325.05103
[8] Ebert, J., A sensitive transitive closure algorithm, Inform. Process. Lett., 12, 5, 225-258 (1981) · Zbl 0468.68066
[9] Eve, J.; Kurki-Suonio, R., On computing the transitive closure of a relation, Acta Informatica, 8, 308-314 (1977) · Zbl 0349.68021
[10] Fischer, M. J.; Meyer, A. R., Boolean matrix multiplication and transitive closure, (12th Ann. IEEE Symp. on Switching and Automata Theory. 12th Ann. IEEE Symp. on Switching and Automata Theory, East Lansing, MI (1971)), 129-131
[11] Fletcher, J. G., A more general algorithm for computing closed semiring costs between vertices of a directed graph, Comm. ACM, 23, 6, 350-351 (1980)
[12] Furman, M. E., Application of a method of fast multiplication of matrices in the problem of finding the transitive closure of graph, Soviet Math. Dokl., 11, 1252 (1970) · Zbl 0214.23602
[13] Hansen, P., A cascade algorithm for the logical closure of a set of binary relations, Inform. Process. Lett., 2, 50-53 (1976) · Zbl 0327.90021
[14] Karp, R. M.; Tarjan, R. E., Linear-time algorithms for connectivity problems, J. Algorithms, 1, 374-399 (1980) · Zbl 0463.68060
[15] Lehmann, D., Algebraic structures for transitive closure, Theoret. Comput. Sci., 4, 59-76 (1977) · Zbl 0358.68061
[16] Munro, I., Efficient determination of the transitive closure of a directed graph, Inform. Process. Lett., 56-58 (1971) · Zbl 0221.68030
[17] O’Neil, P. E.; O’Neil, E. J., A fast expected time algorithm for boolean matrix multiplication and transitive closure, Inform. and Control, 22, 132-138 (1973) · Zbl 0256.65016
[18] Purdom, P., A transitive closure algorithm, BIT, 10, 76-94 (1970) · Zbl 0193.14604
[19] Rote, G., A systolic array for the algebraic path problems, (Rept., Tech. Univ. of Graz (1983), Dept. of Mathematics,: Dept. of Mathematics, Austria)
[20] Roy, B., Transitivité et connexité, Compt. Rend. Acad. Sci. Paris, 249, 216 (1959) · Zbl 0092.15902
[21] Schmitz, L., An improved transitive closure algorithm, Comput., 30, 359-371 (1983) · Zbl 0504.68042
[22] Schnorr, C. P., An algorithm for transitive closure with linear expected time, SIAM J. Comput, 7, 2, 127-133 (1978)
[23] Strassen, V., Gaussian elimination is not optimal, Numer. Math., 13, 354-356 (1969) · Zbl 0185.40101
[24] Sysło, M. M.; Dzikiewicz, J., Computational experiences with some transitive algorithms, Comput., 15, 33-39 (1975) · Zbl 0336.05003
[25] Tarjan, R. E., Depth-first search and linear graph algorithms, SIAM J. Comput., 1, 2, 146-160 (1972) · Zbl 0251.05107
[26] Warren, H. S., A modification of Warshall’s algorithm for the transitive closure of binary relations, Comm. ACM, 18, 4, 218-220 (1975) · Zbl 0309.94048
[27] Warshall, S., A theorem on boolean matrices, J. Assoc. Comput. Mach., 9, 11-12 (1962) · Zbl 0118.33104
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.