An experimental study on approximating k shortest simple paths

DOI10.1145/2630068MaRDI QIDQ2828199zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

heuristicpath approximation\(k\) shortest pathssecond path

Mathematics Subject Classification ID

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)

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

Cites work

• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• A nearly optimal algorithm for approximating replacement paths and \(k\) shortest simple paths in general graphs
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• All-Pairs Almost Shortest Paths
• An efficient algorithm for K shortest simple paths
• An efficient implementation of an algorithm for findingK shortest simple paths
• Automata, Languages and Programming
• Deviation algorithms for ranking shortest paths
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Faster replacement paths
• Finding the k shortest simple paths
• Finding the K Shortest Loopless Paths in a Network
• Finding the k Shortest Paths
• Implementation of algorithms forK shortest loopless 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
• Oracles for Distances Avoiding a Failed Node or Link
• Subcubic equivalences between path, matrix, and triangle problems

Cited in

(5)

• Finding the k shortest simple paths
• Approximating the Canadian traveller problem with online randomization
• Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems
• An experimental study on approximating \(k\) shortest simple paths
• 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)