×

Allowable processing orders in the accelerated cascade algorithm. (English) Zbl 0587.90095

We deal with the ’accelerated’ version of O. Bilde and J. Krarup [Metra 8, 231-241 (1969)] of the ’all shortest distances’ cascade algorithm due to B. A. Farbey, A. H. Land and J. D. Murchland [Manage. Sci., Theory 14, 19-28 (1967; Zbl 0183.236)]. A set of weakest possible conditions on the processing-order for distance-matrix entries, under which the Bilde-Krarup acceleration remains valid, is determined. These conditions are weaker than those of T. C. Hu [SIAM J. Appl. Math. 15, 207-218 and 1517 (1967; Zbl 0158.154)] for the original algorithm, and in particular imply that the simple processing order of the original algorithm remains admissible for the accelerated version.

MSC:

90C35 Programming involving graphs or networks
05C35 Extremal problems in graph theory
65K05 Numerical mathematical programming methods

Software:

Algorithm 97
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bilde, O.; Krarup, J., A modified cascade algorithm for shortest paths, Metra, 8, 231-241 (1969)
[2] Brucker, P., Theory of Matrix Algorithms, (Math. Systems in Economics, 13 (1974), Verlag Anton Hain: Verlag Anton Hain Meisenheim am Glan) · Zbl 0402.90070
[3] Dantzig, G. B., All shortest routes in a graph, (Rosenthiel, P., Theory of Graphs (1967), Gordon and Breach: Gordon and Breach New York), 91-92
[4] Farbey, B. A.; Land, A. H.; Murchland, J. D., The cascade algorithm for finding all shortest distances in a directed graph, Management Sci., 14, 19-33 (1967) · Zbl 0183.23603
[5] Floyd, R. W., Algorithm 97: shortest path, Comm. Assoc. Comput. Mach., 5, 345 (1962)
[6] Goldman, A. J.; Tiwari, P., Allowable processing orders in the cascade algorithm, (Mathematical Sciences Department Technical Report No. 388 (1983), The Johns Hopkins University) · Zbl 0587.90095
[7] Hu, T. C., Revised matrix algorithms for shortest paths, J. SIAM Appl. Math., 15, 207-218 (1967) · Zbl 0158.15404
[8] Kerr, L. R., The effect of algebraic structure on the computational complexity of matrix multiplications, (Ph.D. Thesis (1970), Cornell University) · Zbl 0215.55501
[9] Lehmann, D. J., Algebraic structures for transitive closure, Theoret. Comput. Sci., 4, 59-76 (1977) · Zbl 0358.68061
[10] Nakamori, M., A note on the optimality of some all-shortest-path algorithms, J. Oper. Res. Japan, 15, 201-204 (1972) · Zbl 0253.90059
[11] Pandit, S. N.N., The shortest route problem — an addendum, Oper. Res., 9, 129-132 (1961)
[12] Shier, D. R., Iterative methods for determining the \(k\) shortest paths in a network, Networks, 6, 205-229 (1976) · Zbl 0364.90105
[13] Tomescu, I., Sur les méthodes matricielles dans la théorie des reseaux, C.R. Acad. Sci. Paris, 263, 826-829 (1966) · Zbl 0152.14702
[14] Yen, J. Y., Shortest Path Network Algorithms, (Math. Systems in Economics, 18 (1975), Verlag Anton Hain: Verlag Anton Hain Meisenheim am Glan) · Zbl 0218.90063
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.