On the k Shortest Simple Paths Problem in Weighted Directed Graphs

DOI10.1137/080730950MaRDI QIDQ3068636zbMATH OpenOpenAlexFDO

Authors Liam Roditty

Publication date 17 January 2011

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/080730950

zbMATH Keywords

\(k\) shortest simple pathgraph algorithmssecond shortest pathshortest path

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Recommendations

• On the k-simple shortest paths problem in weighted directed graphs
• The next‐to‐shortest path problem on directed graphs with positive edge weights
• Approximate shortest paths in weighted graphs
• scientific article; zbMATH DE number 1561018
• On the tractability of shortest path problems in weighted edge-coloured graphs
• A sidetrack-based algorithm for finding the k shortest simple paths in a directed graph
• Algorithms and Data Structures
• Automata, Languages and Programming
• Replacement paths and k simple shortest paths in unweighted directed graphs
• On the \(K\) shortest path trees problem

Cited in

(21)

• On the \(K\) shortest path trees problem
• Finding the \(k\) shortest paths in parallel
• An experimental study on approximating k shortest simple paths
• On the k-simple shortest paths problem in weighted directed graphs
• Efficiently listing bounded length \(st\)-paths
• An experimental study on approximating \(k\) shortest simple paths
• Counting approximately-shortest paths in directed acyclic graphs
• On the weights of simple paths in weighted complete graphs
• K\(^{\ast}\): A heuristic search algorithm for finding the \(k\) shortest paths
• Finding k simple shortest paths and cycles
• A sidetrack-based algorithm for finding the k shortest simple paths in a directed graph
• The next‐to‐shortest path problem on directed graphs with positive edge weights
• Finding k shortest simple paths in directed graphs: a node classification algorithm
• Minimal functional routes in directed graphs with dependent edges
• Finding the \(k\) shortest paths in parallel
• A new \(O(m+k n \log \overline{d})\) algorithm to find the \(k\) shortest paths in acyclic digraphs
• Algorithms and Data Structures
• A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs
• Maintaining shortest paths under deletions in weighted directed graphs
• Near optimal algorithm for fault tolerant distance oracle and single source replacement path problem
• Faster algorithm for second (s,t)-mincut and breaking quadratic barrier for dual edge sensitivity for (s,t)-mincut

This page was built for publication: On the k Shortest Simple Paths Problem in Weighted Directed Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3068636)