An experimental study on approximating k shortest simple paths
DOI10.1145/2630068zbMATH Open1347.68367OpenAlexW1977192249MaRDI QIDQ2828199FDOQ2828199
Authors: Asaf Frieder, Liam Roditty 
Publication date: 24 October 2016
Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2630068
Recommendations
- An experimental study on approximating \(k\) shortest simple paths
- On the k Shortest Simple Paths Problem in Weighted Directed Graphs
- On the \(k\)-simple shortest paths problem in weighted directed graphs
- A nearly optimal algorithm for approximating replacement paths and \(k\) shortest simple paths in general graphs
- A sidetrack-based algorithm for finding the \(k\) shortest simple paths in a directed graph
Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Paths and cycles (05C38)
Cites Work
- Finding the k Shortest Paths
- A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Oracles for Distances Avoiding a Failed Node or Link
- All-Pairs Almost Shortest Paths
- Deviation algorithms for ranking shortest paths
- Finding the K Shortest Loopless Paths in a Network
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Finding the k shortest simple paths
- Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems
- On the k Shortest Simple Paths Problem in Weighted Directed Graphs
- An efficient algorithm for K shortest simple paths
- An efficient implementation of an algorithm for findingK shortest simple paths
- Implementation of algorithms forK shortest loopless paths
- Automata, Languages and Programming
- Subcubic equivalences between path, matrix, and triangle problems
- Faster replacement paths
- A nearly optimal algorithm for approximating replacement paths and \(k\) shortest simple paths in general graphs
Cited In (5)
- Finding the k shortest simple paths
- Approximating the Canadian traveller problem with online randomization
- An experimental study on approximating \(k\) shortest simple paths
- Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems
- An efficient implementation of an algorithm for findingK shortest simple paths
This page was built for publication: An experimental study on approximating \(k\) shortest simple paths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2828199)
