On the k Shortest Simple Paths Problem in Weighted Directed Graphs

DOI10.1137/080730950zbMATH Open1209.68707OpenAlexW2041299693MaRDI QIDQ3068636FDOQ3068636

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

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

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)

Cited In (19)

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

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)