Approximate shortest paths in weighted graphs

DOI10.1016/j.jcss.2011.09.001zbMath1237.68248OpenAlexW2094416368MaRDI 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 pathapproximation algorithmweighted graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (2)

Mixing local and global information for community detection in large networks ⋮ A parallel bio-inspired shortest path algorithm

Cites Work

• Unnamed Item
• 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

This page was built for publication: Approximate shortest paths in weighted graphs