Academic
Publications
Subcubic Cost Algorithms for the All Pairs Shortest Path Problem

Subcubic Cost Algorithms for the All Pairs Shortest Path Problem,10.1007/PL00009198,Algorithmica,Tadao Takaoka

Subcubic Cost Algorithms for the All Pairs Shortest Path Problem   (Citations: 29)
BibTex | RIS | RefWorks Download
.    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 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 .
Journal: Algorithmica , vol. 20, no. 3, pp. 309-318, 1998
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...For unweighted directed graphs, the first truly sub-cubic al gorithm was designed by Alon et al. [2], which was improved subsequently by Takaoka [18], and most recently by Zwick [22]...

    Bill Summerset al. On time

    • ...If edge costs are small non-negative integers, the complexity for APSP becomes deeply sub-cubic, i.e., O(n 3−� )f or some �> 0, as shown in [14], [2], [17] and [19]...

    Tadao Takaoka. Efficient Algorithms for the 2Center Problems

    • ...Now, upon the metabolic network (X, Y ) obtained with the previous algorithm, the set of all shortest metabolic pathways of length up to 2k, using the metabolites and reactions in R starting and ending in sets of at most m metabolites among those involved in the reactions in R, can be obtained by using an all-pairs shortest path algorithm (Dijkstra, 1959; Floyd, 1962; Johnson, 1977; Takaoka, 1998) upon each element of C as source vertex ...

    Liliana Félixet al. Efficient Reconstruction of Metabolic Pathways by Bidirectional Chemic...

    • ...For real-weighted sparse graphs, this takes O(mn2 + n3 loglogn) time using a recent O(mn + n2 loglogn) time APSP algorithm [20], and for dense graphs, it takes O(n4 √ loglogn/logn) time using a very recent O(n3 √ loglogn/logn) time APSP algo- rithm [25] (see also [22])...

    Camil Demetrescuet al. Oracles for Distances Avoiding a Failed Node or Link

    • ...Fast matrix multiplication has also been applied to solve APSP in the unweighted directed case [3, 29] (currently the best time bound is O(n 2:575 ) by Zwick [29]), as well as the weighted undirected/directed cases [3, 12, 19, 23, 29] when the weights are small integers (subcubic time bounds hold when weights are at most n 0:634 [19, 29])...

    Timothy M. Chan. All-pairs shortest paths for unweighted undirected graphs in o(mn) tim...

Sort by: