article

On the all-pairs shortest-path algorithm of Moffat and Takaoka

Authors:

Kurt Mehlhorn,

Volker PriebeAuthors Info & Claims

Random Structures & Algorithms, Volume 10, Issue 1-2

Pages 205 - 220

Published: 01 February 1997 Publication History

Abstract

No abstract available.

Cited By

View all

Fong KLi MLiang HYang LYuan H(2016)Average-case complexity of the min-sum matrix product problemTheoretical Computer Science10.1016/j.tcs.2015.09.008609:P1(76-86)Online publication date: 4-Jan-2016
https://dl.acm.org/doi/10.1016/j.tcs.2015.09.008
Fong KLi MLiang HYang LYuan H(2014)Average-Case Complexity of the Min-Sum Matrix Product ProblemAlgorithms and Computation10.1007/978-3-319-13075-0_4(41-52)Online publication date: 15-Dec-2014
https://dl.acm.org/doi/10.1007/978-3-319-13075-0_4
Peres YSotnikov DSudakov BZwick U(2013)All-pairs shortest paths in O(n2) time with high probabilityJournal of the ACM10.1145/2508028.250598860:4(1-25)Online publication date: 4-Sep-2013
https://dl.acm.org/doi/10.1145/2508028.2505988
Show More Cited By

Index Terms

On the all-pairs shortest-path algorithm of Moffat and Takaoka
1. Mathematics of computing
  1. Probability and statistics
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Design and analysis of algorithms

Recommendations

A Multiple Pairs Shortest Path Algorithm

The multiple pairs shortest path problem (MPSP) arises in many applications where the shortest paths and distances between only some specific pairs of origin-destination (OD) nodes in a network are desired. The traditional repeated single-source shortest ...
Solving all-pairs shortest path by single-source computations

Given an arbitrary directed graph G=(V,E) with non-negative edge lengths, we present an algorithm that computes all pairs shortest paths in time O(mn+mlgn+nT(m,n)), where m is the number of different edges contained in shortest paths and T(m,n) is the ...
On the difficulty of some shortest path problems

We prove superlinear lower bounds for some shortest path problems in directed graphs, where no such bounds were previously known. The central problem in our study is the replacement paths problem: Given a directed graph G with non-negative edge weights, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Random Structures & Algorithms

Random Structures & Algorithms Volume 10, Issue 1-2

Special issue: average-case analysis of algorithms

Jan.–March 1997

296 pages

ISSN:1042-9832

EISSN:1098-2418

Editors:
Michal Karoński
Adam Mickiewicz Univ., Poznzn´;Poland; and Emory Univ., Atlanta, GA
,
Joel Spencer
New York Univ., New York
,
Philippe Flajote
INRIA
,
Wojciech Szpankowski
INRIA

Issue’s Table of Contents

Publisher

John Wiley & Sons, Inc.

United States

Publication History

Published: 01 February 1997

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Fong KLi MLiang HYang LYuan H(2016)Average-case complexity of the min-sum matrix product problemTheoretical Computer Science10.1016/j.tcs.2015.09.008609:P1(76-86)Online publication date: 4-Jan-2016
https://dl.acm.org/doi/10.1016/j.tcs.2015.09.008
Fong KLi MLiang HYang LYuan H(2014)Average-Case Complexity of the Min-Sum Matrix Product ProblemAlgorithms and Computation10.1007/978-3-319-13075-0_4(41-52)Online publication date: 15-Dec-2014
https://dl.acm.org/doi/10.1007/978-3-319-13075-0_4
Peres YSotnikov DSudakov BZwick U(2013)All-pairs shortest paths in O(n2) time with high probabilityJournal of the ACM10.1145/2508028.250598860:4(1-25)Online publication date: 4-Sep-2013
https://dl.acm.org/doi/10.1145/2508028.2505988
Takaoka T(2013)A simplified algorithm for the all pairs shortest path problem with O(n2logn) expected timeJournal of Combinatorial Optimization10.1007/s10878-012-9550-325:2(326-337)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1007/s10878-012-9550-3
Takaoka THashim M(2010)A simpler algorithm for the all pairs shortest path problem with o(n2 log n) expected timeProceedings of the 4th international conference on Combinatorial optimization and applications - Volume Part II10.5555/1940424.1940440(195-206)Online publication date: 18-Dec-2010
https://dl.acm.org/doi/10.5555/1940424.1940440
Meyer U(2003)Average-case complexity of single-source shortest-paths algorithmsJournal of Algorithms10.1016/S0196-6774(03)00046-448:1(91-134)Online publication date: 1-Aug-2003
https://dl.acm.org/doi/10.1016/S0196-6774%2803%2900046-4
Meyer UKosaraju S(2001)Single-source shortest-paths on arbitrary directed graphs in linear average-case timeProceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms10.5555/365411.365784(797-806)Online publication date: 9-Jan-2001
https://dl.acm.org/doi/10.5555/365411.365784
Galli N(2000)Average Costs of a Graph ExplorationJournal of Algorithms10.1006/jagm.1999.105334:1(148-176)Online publication date: 1-Jan-2000
https://dl.acm.org/doi/10.1006/jagm.1999.1053
Subramanian CTarjan RWarnow T(1999)A generalization of Janson inequalities and its application to finding shortest pathsProceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms10.5555/314500.314917(795-804)Online publication date: 1-Jan-1999
https://dl.acm.org/doi/10.5555/314500.314917
Tamaki HTokuyama TKarloff H(1998)Algorithms for the maximum subarray problem based on matrix multiplicationProceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms10.5555/314613.314823(446-452)Online publication date: 1-Jan-1998
https://dl.acm.org/doi/10.5555/314613.314823
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Index Terms

Recommendations

A Multiple Pairs Shortest Path Algorithm

Solving all-pairs shortest path by single-source computations

On the difficulty of some shortest path problems

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations