Abstract
In this paper we give three sub-cubic cost algorithms for the all pairs shortest distance (APSD) and path (APSP) problems. The first is a parallel algorithm that solves the APSD problem for a directed graph with unit edge costs in O(log2 n) time with \(O({{n^\mu } \mathord{\left/{\vphantom {{n^\mu } {\sqrt {\log n} }}} \right.\kern-\nulldelimiterspace} {\sqrt {\log n} }})\) processors where Μ=2.688 on an EREW-PRAM. The second parallel algorithm solves the APSP, and consequently APSD, problem for a directed graph with non-negative general costs (real numbers) in O(log2 n) time with o(n3) subcubic cost. Previously this cost was greater than O(n3). Finally we improve with respect to M the complexity O((Mn)μ) of a sequential algorithm for a graph with edge costs up to M into O(M1/3 n 6+1/3/3(log n)2/3(log log n)1/3) in the APSD problem.
Partially supported by Grant-in-aid No. 07680332 by Monbusho Scientific Research Program and a research grant from Hitachi Engineering Co., Ltd.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
N. Alon, Z. Galil and O. Margalit, On the exponent of the all pairs shortest path problem, Proc. 32th IEEE FOCS (1991), pp 569–575.
N. Alon, Z. Galil, and O. Margalit and M. Naor, Witnesses for Boolean matrix multiplication and for shortest paths, Proc. 33th IEEE FOCS (1992), pp. 417–426.
D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation 9 (1990), pp. 251–280.
E. Dekel, D. Nassimi and S. Sahni, Parallel matix and graph algorithms, SIAM Jour. on Comp. 10 (1981), pp. 657–675.
M. L. Fredman, New bounds on the complexity of the shortest path problem, SIAM Jour. Comput. 5 (1976), pp. 49–60.
H. Gazit and G. Miller, An improved parallel algorithm that computes the bis numbering of a directed graph, Info. Proc. Lett. 28 (1988) pp. 61–65.
A. Gibbons and W. Rytter, Efficient Parallel Algorithms, Cambridge Univ. Press (1988).
Y. Han, V. Pan and J. Reif, Efficient parallel algorithms for computing all pairs shortest paths in directed graphs. Proc. 4th ACM SPAA (1992), pp. 353–362.
F. Romani, Shortest-path problem is not harder than matrix multiplications, Info. Proc. Lett. 11 (1980) pp.134–136.
R. Scidel, On the all-pairs-shortest-path problem, Proc. 24th ACM STOC (1990), pp. 213–223.
A. Schönhage and V. Strassen, Schnelle Multiplikation Gro\er Zahlen, Computing 7 (1971) pp. 281–292.
T. Takaoka, A new upperbound on the complexity of the all pairs shortest path problem, Info. Proc. Lett. 43 (1992), pp. 195–199.
T. Takaoka, An efficient parallel algorithm for the all pairs shortest path problem, WG 88, Lecture Notes in Computer Science 344 (Springer, Berlin, 1988) pp. 276–287.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Takaoka, T. (1995). Sub-cubic cost algorithms for the all pairs shortest path problem. In: Nagl, M. (eds) Graph-Theoretic Concepts in Computer Science. WG 1995. Lecture Notes in Computer Science, vol 1017. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60618-1_86
Download citation
DOI: https://doi.org/10.1007/3-540-60618-1_86
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60618-5
Online ISBN: 978-3-540-48487-5
eBook Packages: Springer Book Archive