External matrix multiplication and all-pairs shortest path

DOI10.1016/J.IPL.2004.03.015MaRDI QIDQ2390290zbMATH OpenOpenAlexFDO

Authors Jop F. Sibeyn

Publication date 21 July 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2004.03.015

zbMATH Keywords

all-pairs shortest pathsexternal algorithmsgraph algorithmsmatrix multiplication

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Recommendations

• Algorithms – ESA 2005
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• Applications of shortest path algorithms to matrix scalings
• Fast algorithms for (, )-matrix multiplication and bottleneck shortest paths
• Matrix Searching with the Shortest-Path Metric
• A new matrix operator-based algorithm for the shortest path problem
• On the exponent of all pairs shortest path problem
• On Compact Representations of All-Pairs-Shortest-Path-Distance Matrices
• On compact representations of all-pairs-shortest-path-distance matrices

Cites work

• A new upper bound on the complexity of the all pairs shortest path problem
• Algorithms for memory hierarchies. Advanced lectures
• Algorithms for parallel memory, I: Two-level memories
• Efficient parallel algorithms for computing all pair shortest paths in directed graphs
• Gaussian elimination is not optimal
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• Matrix multiplication via arithmetic progressions
• The input/output complexity of transitive closure

This page was built for publication: External matrix multiplication and all-pairs shortest path

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