Approximate shortest paths in weighted graphs
From MaRDI portal
Publication:414929
DOI10.1016/J.JCSS.2011.09.001zbMATH Open1237.68248OpenAlexW2094416368MaRDI QIDQ414929FDOQ414929
Authors: 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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Distance in graphs (05C12) Paths and cycles (05C38)
Cites Work
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Efficient Algorithms for Shortest Paths in Sparse Networks
- Faster scaling algorithms for general graph matching problems
- All-Pairs Almost Shortest Paths
- Matrix multiplication via arithmetic progressions
- More algorithms for all-pairs shortest paths in weighted graphs
- Scaling Algorithms for the Shortest Paths Problem
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Title not available (Why is that?)
- On the exponent of all pairs shortest path problem
- An algorithm for finding all shortest paths using \(N^{2\cdot 81}\) infinite-precision multiplications
- All-Pairs Shortest Paths with a Sublinear Additive Error
Cited In (23)
- Mixing local and global information for community detection in large networks
- Shortest Paths with Bundles and Non-additive Weights Is Hard
- On paths with the shortest average arc length in weighted graphs
- Approximately counting approximately-shortest paths in directed acyclic graphs
- Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
- Title not available (Why is that?)
- A parallel bio-inspired shortest path algorithm
- Shortest paths with ordinal weights
- APPROXIMATE SHORTEST HOMOTOPIC PATHS IN WEIGHTED REGIONS
- Improved preprocessing, labeling and scaling algorithms for the Weight-Constrained Shortest Path Problem
- Near-optimal algorithms for shortest paths in weighted unit-disk graphs
- Maintaining shortest paths under deletions in weighted directed graphs
- A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs
- On the k Shortest Simple Paths Problem in Weighted Directed Graphs
- Algorithms and Data Structures
- Approximating Shortest Paths in Graphs
- Lightweight paths in graphs
- All-Pairs Shortest Paths with a Sublinear Additive Error
- Shortest paths in networks with vector weights
- The summation and bottleneck minimization for single-step searching on weighted graphs
- Title not available (Why is that?)
- Successive shortest paths in complete graphs with random edge weights
- All-Pairs Almost Shortest Paths
This page was built for publication: Approximate shortest paths in weighted graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414929)
