An all-pairs shortest path algorithm for bipartite graphs

DOI10.2478/S13537-013-0110-4MaRDI QIDQ469055zbMATH OpenOpenAlexFDO

Authors Svetlana Torgasin, Karl-Heinz Zimmermann

Publication date 10 November 2014

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

bipartite graphshortest pathdistance matrix producttropical (MIN-plus) algebra

Mathematics Subject Classification ID

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

Recommendations

• An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs
• Solving the all-pairs-shortest-length problem on chordal bipartite graphs
• Optimal computation of shortest paths on doubly convex bipartite graphs
• Unified all-pairs shortest path algorithms in the chordal hierarchy
• Solving the shortest-paths problem on bipartite permutation graphs efficiently

Cites work

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

Cited in

(5)

• All pairs shortest paths for graphs with small integer length edges
• On the complexity of average path length for biological networks and patterns
• All-pairs bottleneck paths in vertex weighted graphs
• scientific article; zbMATH DE number 5289563 (Why is no real title available?)
• Optimal computation of shortest paths on doubly convex bipartite graphs

Describes a project that uses

Uses Software

• Algorithm 97
• CUDA

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

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