Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems
From MaRDI portal
Publication:976116
DOI10.1016/j.ipl.2008.12.015zbMath1193.68193OpenAlexW2094099891MaRDI QIDQ976116
Zvi Gotthilf, Moshe Lewenstein
Publication date: 16 June 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2008.12.015
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (12)
The \(k\)-dissimilar vehicle routing problem ⋮ On the Power of Tree-Depth for Fully Polynomial FPT Algorithms ⋮ Enumerating \(K\) best paths in length order in DAGs ⋮ Ranking robustness and its application to evacuation planning ⋮ An efficient time and space \(K\) point-to-point shortest simple paths algorithm ⋮ Path-driven orientation of mixed graphs ⋮ A new $O(m+k n log overline{d})$ algorithm to find the $k$ shortest paths in acyclic digraphs ⋮ Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles ⋮ An Experimental Study on Approximating k Shortest Simple Paths ⋮ Incremental distance products via faulty shortest paths ⋮ Ranking One Million Simple Paths in Road Networks ⋮ N-gram distribution and unification gain problem and its optimal solution
Cites Work
- Unnamed Item
- A note on two problems in connexion with graphs
- The k most vital arcs in the shortest path problem
- A new approach to all-pairs shortest paths on real-weighted graphs
- More algorithms for all-pairs shortest paths in weighted graphs
- An efficient algorithm for K shortest simple paths
- Finding the k Shortest Paths
- Fibonacci heaps and their uses in improved network optimization algorithms
- 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: Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems
