An efficient algorithm for K shortest simple paths
From MaRDI portal
Publication:3956415
DOI10.1002/net.3230120406zbMath0493.68068OpenAlexW2078948975MaRDI QIDQ3956415
Toshihide Ibaraki, Naoki Katoh, Hisashi Mine
Publication date: 1982
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.3230120406
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)
Related Items
The hierarchical network design problem, Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context, An algorithm for ranking quickest simple paths, Finding \(K\) shortest looping paths in a traffic-light network, Finding the k shortest paths in parallel, Computing and listing \(st\)-paths in public transportation networks, A comprehensive survey on the quickest path problem, An exact lexicographic approach for the maximally risk-disjoint/minimal cost path pair problem in telecommunication networks, A new exact algorithm for the vehicle routing problem based on \(q\)-paths and \(k\)-shortest paths relaxations, The k most vital arcs in the shortest path problem, Multiobjective routing problems, Approximating the Canadian traveller problem with online randomization, Internet packet routing: application of a \(K\)-quickest path algorithm, Enumerating \(K\) best paths in length order in DAGs, Efficiently Listing Bounded Length st-Paths, How much the grid network and rescuers' communication can improve the rescue efficiency in worst-case analysis, On the second point-to-point undirected shortest simple path problem, Finding \(K\) dissimilar paths: single-commodity and discretized flow formulations, An interactive approach to identify the best compromise solution for two objective shortest path problems, An efficient time and space \(K\) point-to-point shortest simple paths algorithm, Finding the first \(K\) shortest paths in a time-window network., Computational experiments with a lazy version of a \(K\) quickest simple path ranking algorithm, On finding dissimilar paths, Element perturbation problems of optimum spanning trees with two-parameter objectives, An algorithm for finding the \(k\) quickest paths in a network, Multicriteria path and tree problems: discussion on exact algorithms and applications, Finding the \(K\) shortest paths in a schedule-based transit network, Computing and Listing st-Paths in Public Transportation Networks, The first \(K\) shortest unique-arc walks in a traffic-light network, Improved algorithms for replacement paths problems in restricted graphs, Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems, An algorithm for determining the K-best solutions of the one-dimensional Knapsack problem, Finding \(K\) shortest looping paths with waiting time in a time--window network, A new $O(m+k n log overline{d})$ algorithm to find the $k$ shortest paths in acyclic digraphs, Solving the \(k\)-shortest path problem with time windows in a time varying network, Unnamed Item, First passage percolation on locally treelike networks. I. Dense random graphs, An Experimental Study on Approximating k Shortest Simple Paths, Voronoi diagrams with barriers and on polyhedra for minimal path planning, Distance confined path problem and separable integer programming, On the \(K\) shortest path trees problem, Finding the k Shortest Paths, DEVIATION ALGORITHMS FOR RANKING SHORTEST PATHS, Ranking One Million Simple Paths in Road Networks, Optimal shortest path set problem in undirected graphs, Finding the \(k\) quickest simple paths in a network
Cites Work
