ISSN:
1432-0541
Keywords:
Key words. All pairs shortest path problem, Parallel algorithm, Unit cost problem, General cost problem, Two-phase algorithm.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. In this paper we give three subcubic 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(log 2 n) time with $O(n^\mu/\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 nonnegative general costs (real numbers) in O(log 2 n) time with o(n 3 ) subcubic cost. Previously this cost was greater than O(n 3 ) . Finally we improve with respect to M the complexity O((Mn) μ ) of a sequential algorithm for a graph with edge costs up to M to O(M 1/3 n (6+ω)/3 (log n) 2/3 (log log n) 1/3 ) in the APSD problem, where ω = 2.376 .
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00009198
Permalink