An all-pairs shortest path algorithm for bipartite graphs

DOI10.2478/s13537-013-0110-4zbMath1298.05309OpenAlexW2132602186MaRDI QIDQ469055

Karl-Heinz Zimmermann, Svetlana Torgasin

Publication date: 10 November 2014

Published in: Central European Journal of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2478/s13537-013-0110-4

zbMATH Keywords

shortest pathbipartite graphdistance matrix producttropical (MIN-plus) algebra

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Uses Software

• CUDA
• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• Solving the all-pairs-shortest-length problem on chordal bipartite graphs
• Solving the shortest-paths problem on bipartite permutation graphs efficiently
• A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths
• Matrix multiplication via arithmetic progressions
• Subcubic cost algorithms for the all pairs shortest path problem
• Gaussian elimination is not optimal
• A more efficient algorithm for the min-plus multiplication
• New Bounds on the Complexity of the Shortest Path Problem
• Efficient Algorithms for Shortest Paths in Sparse Networks
• All-Pairs Almost Shortest Paths
• Estimating all pairs shortest paths in restricted graph families: a unified approach
• A Theorem on Boolean Matrices

This page was built for publication: An all-pairs shortest path algorithm for bipartite graphs