Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems

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

zbMATH Keywords

algorithmsshortest pathsweighted directed graphsreplacement paths\(k\) simple shortest paths

Mathematics Subject Classification ID

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