A simpler algorithm for the all pairs shortest path problem with O(n ^2 n) expected time

DOI10.1007/978-3-642-17461-2_16MaRDI QIDQ3066458zbMATH OpenOpenAlexFDO

Authors Tadao Takaoka, Mashitoh Hashim

Publication date 10 January 2011

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-17461-2_16

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Programming involving graphs or networks (90C35)

Recommendations

• A simplified algorithm for the all pairs shortest path problem with \(O(n ^{2} \log n)\) expected time
• On the all-pairs shortest path algorithm of Moffat and Takaoka
• scientific article; zbMATH DE number 986995
• scientific article; zbMATH DE number 3908469
• An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$

Cited in

(10)

• An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem
• A simplified algorithm for the all pairs shortest path problem with \(O(n ^{2} \log n)\) expected time
• scientific article; zbMATH DE number 986995 (Why is no real title available?)
• scientific article; zbMATH DE number 3908469 (Why is no real title available?)
• scientific article; zbMATH DE number 219247 (Why is no real title available?)
• scientific article; zbMATH DE number 913360 (Why is no real title available?)
• A forward-backward single-source shortest paths algorithm
• Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time
• On the all-pairs shortest path algorithm of Moffat and Takaoka
• Efficient supply chains in agriculture through cluster-based route optimization

This page was built for publication: A simpler algorithm for the all pairs shortest path problem with \(O(n ^{2} \log n)\) expected time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3066458)