An Experimental Study on Approximating k Shortest Simple Paths

DOI10.1145/2630068zbMath1347.68367OpenAlexW1977192249MaRDI QIDQ2828199

Liam Roditty, Asaf Frieder

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

zbMATH Keywords

heuristic\(k\) shortest pathspath approximationsecond path

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)

Related Items (1)

Approximating the Canadian traveller problem with online randomization

Cites Work

• Unnamed Item
• Unnamed Item
• Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems
• On the k Shortest Simple Paths Problem in Weighted Directed Graphs
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• Oracles for Distances Avoiding a Failed Node or Link
• Implementation of algorithms forK shortest loopless paths
• An efficient algorithm for K shortest simple paths
• Finding the k Shortest Paths
• An efficient implementation of an algorithm for findingK shortest simple paths
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Subcubic Equivalences Between Path, Matrix, and Triangle Problems
• All-Pairs Almost Shortest Paths
• Finding the k shortest simple paths
• DEVIATION ALGORITHMS FOR RANKING SHORTEST PATHS
• Finding the K Shortest Loopless Paths in a Network
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• Automata, Languages and Programming

This page was built for publication: An Experimental Study on Approximating k Shortest Simple Paths