Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(4)
allpairs shortest path
Directed Graph
Parallel Algorithm
APSP
Subscribe
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
Edit
Subcubic Cost Algorithms for the All Pairs Shortest Path Problem
(
Citations: 29
)
BibTex

RIS

RefWorks
Download
Tadao Takaoka
. 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. 309318, 1998
DOI:
10.1007/PL00009198
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.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.informatik.unitrier.de
)
(
www.springerlink.com
)
(
www.springerlink.com
)
More »
Citation Context
(17)
...For unweighted directed graphs, the first truly subcubic al gorithm was designed by Alon et al. [2], which was improved subsequently by Takaoka [
18
], and most recently by Zwick [22]...
Bill Summers
,
et al.
On time
...If edge costs are small nonnegative integers, the complexity for APSP becomes deeply subcubic, 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 allpairs shortest path algorithm (Dijkstra, 1959; Floyd, 1962; Johnson, 1977;
Takaoka, 1998
) upon each element of C as source vertex ...
Liliana Félix
,
et al.
Efficient Reconstruction of Metabolic Pathways by Bidirectional Chemic...
...For realweighted 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 Demetrescu
,
et 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
.
Allpairs shortest paths for unweighted undirected graphs in o(mn) tim...
References
(14)
Matrix Multiplication via Arithmetic Progressions
(
Citations: 849
)
Don Coppersmith
,
Shmuel Winograd
Journal:
Journal of Symbolic Computation  JSC
, vol. 9, no. 3, pp. 251280, 1990
A New Upper Bound on the Complexity of the All Pairs Shortest Path Problem
(
Citations: 67
)
Tadao Takaoka
Journal:
Information Processing Letters  IPL
, vol. 43, no. 4, pp. 195199, 1992
An Improved Parallel Algorithm that Computes the BFS Numbering of a Directed Graph
(
Citations: 52
)
Hillel Gazit
,
Gary L. Miller
Journal:
Information Processing Letters  IPL
, vol. 28, no. 2, pp. 6165, 1988
On the Exponent of the All Pairs Shortest Path Problem
(
Citations: 72
)
Noga Alon
,
Zvi Galil
,
Oded Margalit
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 569575, 1991
Witnesses for Boolean Matrix Multiplication and for Shortest Paths
(
Citations: 35
)
Noga Alon
,
Zvi Galilt
,
Oded Margalit
,
Moni Naor
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 417426, 1992
Sort by:
Citations
(29)
On time
(
Citations: 19
)
Bill Summers
,
Vishrut Goyal
,
Sandeep Sen
Journal:
New Scientist  NEW SCI
, vol. 212, no. 2835, pp. 3434, 2011
Efficient Algorithms for the 2Center Problems
Tadao Takaoka
Conference:
Computational Science and Its Applications  ICCSA
, pp. 519532, 2010
Allpairs nearly 2approximate shortest paths in O ( n 2 polylog n ) time
(
Citations: 3
)
Surender Baswana
,
Vishrut Goyal
,
Sandeep Sen
Journal:
Theoretical Computer Science  TCS
, vol. 410, no. 1, pp. 8493, 2009
Fast algorithms for (max, min)matrix multiplication and bottleneck shortest paths
(
Citations: 4
)
Ran Duan
,
Seth Pettie
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 384391, 2009
Efficient Reconstruction of Metabolic Pathways by Bidirectional Chemical Search
(
Citations: 1
)
Liliana Félix
,
Francesc Rosselló
,
Gabriel Valiente
Journal:
Bulletin of Mathematical Biology  BULL MATH BIOL
, vol. 71, no. 3, pp. 750769, 2009