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
(3)
allpairs shortest path
Matrix Multiplication
APSP
Related Publications
(9)
On the AllPairs...
All Pairs Shortest Paths for Graphs with Small Integer Length Edges
All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication
On the allpairs...
A note on two problems in connection with graphs
Subscribe
Academic
Publications
All Pairs Shortest Paths in Undirected Graphs with Integer Weights
All Pairs Shortest Paths in Undirected Graphs with Integer Weights,10.1109/SFFCS.1999.814635,Avi Shoshan,Uri Zwick
Edit
All Pairs Shortest Paths in Undirected Graphs with Integer Weights
(
Citations: 49
)
BibTex

RIS

RefWorks
Download
Avi Shoshan
,
Uri Zwick
We show that the All Pairs Shortest Paths (APSP) problem for undirected graphs with integer edge weights taken from the range can be solved using only a loga rithmic number of distance products of matrices with ele ments in the range . As a result, we get an algorithm for the
APSP
problem in such graphs that runs in time, where is the number of vertices in the input graph, is the largest edge weight in the graph, and is the exponent of matrix multiplication. This improves, and also simplifies, an time algorithm of Galil and Margalit.
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 605615, 1999
DOI:
10.1109/SFFCS.1999.814635
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.
(
ieeexplore.ieee.org
)
(
ieeexplore.ieee.org
)
Citation Context
(36)
...For APSP in undirected graphs with edges weights from {0,1, ..., M }, Shoshan and Zwick [
16
] desiged an ˜ O(Mn!) algorithm...
Bill Summers
,
et al.
On time
...Much of the prominent work in this area [20, 12,
22
, 26] has developed fast algorithms for certain interesting cases of the allpairs shortest paths (APSP) problem in truly subcubic time, i.e...
Virginia Vassilevska
,
et al.
All Pairs Bottleneck Paths and MaxMin Matrix Products in Truly Subcub...
...For all pairs shortest paths problem with integer weights in undirected graphs, an ˜ O(N · n 2.38 ) time bound algorithm was described by Shoshan and Zwick in [
4
], where ˜ O(f (n)) is the abbreviation for O(f (n) · (log n) t )f or some constantt and N is the largest edge weight in the graph...
Xiaofeng Gu
,
et al.
Improved Algorithms for Detecting Negative Cost Cycles in Undirected G...
...For APSP in undirected graphs with edge weights from {0, 1, ..., M }, Shoshana and Vick [
28
] designed an ˜ O( Mn ω ) algorithm...
Sandeep Sen
.
Approximating Shortest Paths in Graphs
...Betweenness centrality is closely related to All Pairs Shortest Paths Problems (APSP) and algebraic methods have been very successful in obtaining better running times for APSP ([30], [1], [
32
], [15], [8], [34])...
Shiva Kintali
.
Betweenness Centrality : Algorithms and Lower Bounds
References
(25)
All pairs lightest shortest paths
(
Citations: 10
)
Uri Zwick
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 6169, 1999
All Pairs Shortest Paths in Weighted Directed Graphs ¾ Exact and Almost Exact Algorithms
(
Citations: 41
)
Uri Zwick
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 310319, 1998
Subcubic Cost Algorithms for the All Pairs Shortest Path Problem
(
Citations: 29
)
Tadao Takaoka
Journal:
Algorithmica
, vol. 20, no. 3, pp. 309318, 1998
Matrix Multiplication via Arithmetic Progressions
(
Citations: 849
)
Don Coppersmith
,
Shmuel Winograd
Journal:
Journal of Symbolic Computation  JSC
, vol. 9, no. 3, pp. 251280, 1990
All Pairs Shortest Distances for Graphs with Small Integer Length Edges
(
Citations: 32
)
Zvi Galil
,
Oded Margalit
Journal:
Information and Computation/information and Control  IANDC
, vol. 134, no. 2, pp. 103139, 1997
Sort by:
Citations
(49)
On time
(
Citations: 19
)
Bill Summers
,
Vishrut Goyal
,
Sandeep Sen
Journal:
New Scientist  NEW SCI
, vol. 212, no. 2835, pp. 3434, 2011
Nondecreasing paths in a weighted graph or: How to optimally read a train schedule
Virginia Vassilevska Williams
Journal:
ACM Transactions on Algorithms  TALG
, vol. 6, no. 4, pp. 124, 2010
Regularity Lemmas and Combinatorial Algorithms
(
Citations: 5
)
Nikhil Bansal
,
Ryan Williams
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 745754, 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
All Pairs Bottleneck Paths and MaxMin Matrix Products in Truly Subcubic Time
Virginia Vassilevska
,
Ryan Williams
,
Raphael Yuster
Journal:
Theory of Computing
, vol. 5, no. 1, pp. 173189, 2009