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

graph algorithmsshortest pathsecond shortest path\(k\) shortest simple 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

(19)

• Algorithms and Data Structures
• Minimal functional routes in directed graphs with dependent edges
• On the \(k\)-simple shortest paths problem in weighted directed graphs
• The next‐to‐shortest path problem on directed graphs with positive edge weights
• 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
• Counting approximately-shortest paths in directed acyclic graphs
• An experimental study on approximating \(k\) shortest simple paths
• An experimental study on approximating \(k\) shortest simple paths
• K\(^{\ast}\): A heuristic search algorithm for finding the \(k\) shortest paths
• On the weights of simple paths in weighted complete graphs
• Finding \(k\) shortest simple paths in directed graphs: a node classification algorithm
• Efficiently listing bounded length \(st\)-paths
• Finding the \(k\) shortest paths in parallel
• A sidetrack-based algorithm for finding the \(k\) shortest simple paths in a directed graph
• Maintaining shortest paths under deletions in weighted directed graphs
• A nearly optimal algorithm for approximating replacement paths and \(k\) shortest simple paths in general graphs
• Finding \(k\) simple shortest paths and cycles
• On the \(K\) shortest path trees problem

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)