Finding the k shortest simple paths

DOI10.1145/1290672.1290682zbMath1446.68118OpenAlexW4376522482MaRDI QIDQ4962685

Matthew Maxel, Subhash Suri, J. E. Hershberger

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1290672.1290682

zbMATH Keywords

directed pathsreplacement pathsloop-free pathspath equivalence class

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (13)

The \(k\)-dissimilar vehicle routing problem ⋮ Improved formulations for minimum connectivity network interdiction problems ⋮ Approximating the Canadian traveller problem with online randomization ⋮ Unnamed Item ⋮ Enumerating \(K\) best paths in length order in DAGs ⋮ Faster replacement paths algorithms in case of edge or node failure for undirected, positive integer weighted graphs ⋮ Multiple space debris collecting mission -- debris selection and trajectory optimization ⋮ An efficient time and space \(K\) point-to-point shortest simple paths algorithm ⋮ The global optimal algorithm of reliable path finding problem based on backtracking method ⋮ Creating improvisations on chord progressions using suffix trees ⋮ An Experimental Study on Approximating k Shortest Simple Paths ⋮ On the \(K\) shortest path trees problem ⋮ Ranking One Million Simple Paths in Road Networks

This page was built for publication: Finding the k shortest simple paths