Approximate shortest paths in weighted graphs

DOI10.1016/j.jcss.2011.09.001zbMath1237.68248MaRDI QIDQ414929

Raphael Yuster

Publication date: 11 May 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2011.09.001

zbMATH Keywords

shortest path; approximation algorithm; weighted graph

Mathematics Subject Classification ID

05C38: Paths and cycles

05C12: Distance in graphs

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

Mixing local and global information for community detection in large networks

Cites Work

• Matrix multiplication via arithmetic progressions
• An algorithm for finding all shortest paths using \(N^{2\cdot 81}\) infinite-precision multiplications
• On the exponent of all pairs shortest path problem
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• All-Pairs Shortest Paths with a Sublinear Additive Error
• More algorithms for all-pairs shortest paths in weighted graphs
• Efficient Algorithms for Shortest Paths in Sparse Networks
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Faster scaling algorithms for general graph matching problems
• Scaling Algorithms for the Shortest Paths Problem
• All-Pairs Almost Shortest Paths
• Unnamed Item