Finding the \(k\) quickest simple paths in a network
From MaRDI portal
Publication:1322119
DOI10.1016/0020-0190(94)00008-5zbMath0804.90129OpenAlexW2052497422MaRDI QIDQ1322119
Publication date: 9 June 1994
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(94)00008-5
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Graph theory (including graph drawing) in computer science (68R10)
Related Items (38)
A label-setting algorithm for finding a quickest path ⋮ An algorithm for ranking quickest simple paths ⋮ Fast and fine quickest path algorithm ⋮ Finding the k shortest paths in parallel ⋮ Calculation of minimal capacity vectors through \(k\) minimal paths under budget and time constraints ⋮ A comprehensive survey on the quickest path problem ⋮ Reliability of spare routing via intersectional minimal paths within budget and time constraints by simulation ⋮ An efficient alternative to the exact evaluation of the quickest path flow network reliability problem ⋮ Min‐Max quickest path problems ⋮ Routing scheme of a multi-state computer network employing a retransmission mechanism within a time threshold ⋮ Algorithms for the quickest path problem and the reliable quickest path problem ⋮ Internet packet routing: application of a \(K\)-quickest path algorithm ⋮ Algorithms for the quickest time distribution of dynamic stochastic-flow networks ⋮ Binary-state line assignment optimization to maximize the reliability of an information network under time and budget constraints ⋮ The energy-constrained quickest path problem ⋮ A method to evaluate routing policy through \(p\) minimal paths for stochastic case ⋮ System reliability for quickest path problems under time threshold and budget ⋮ Computational experiments with a lazy version of a \(K\) quickest simple path ranking algorithm ⋮ Stochastic flow networks via multiple paths under time threshold and budget constraint ⋮ Backup reliability assessment within tolerable packet error rate for a multi-state unreliable vertex computer network ⋮ Distribution and reliability evaluation of MAX-flow in dynamic multi-state flow networks ⋮ Spare routing problem with \(p\) minimal paths for time-based stochastic flow networks ⋮ On transmission time through \(k\) minimal paths of a capacitated-flow network ⋮ A new $O(m+k n log overline{d})$ algorithm to find the $k$ shortest paths in acyclic digraphs ⋮ Network reliability for multipath TCP networks with a retransmission mechanism under the time constraint ⋮ System Reliability Assessment throughpMinimal Paths in Stochastic Case with Backup-routing ⋮ Reliability evaluation subject to assured accuracy rate and time for stochastic unreliable-node computer networks ⋮ Time version of the shortest path problem in a stochastic-flow network ⋮ Reliability based assignment in stochastic-flow freight network ⋮ Finding the k Shortest Paths ⋮ Two-best solutions under distance constraints: The model and exemplary results for matroids ⋮ Backup reliability of stochastic imperfect-node computer networks subject to packet accuracy rate and time constraints ⋮ Assessment of spare reliability for multi-state computer networks within tolerable packet unreliability ⋮ Fast data transmission and maximal dynamic flow. ⋮ Reliability evaluation of a multistate network subject to time constraint under routing policy ⋮ Spare Reliability for Capacitated Computer Networks Under Tolerable Error Rate and Latency Considerations ⋮ The Maximum Capacity Shortest Path Problem: Generation of Efficient Solution Sets ⋮ Extend the quickest path problem to the system reliability evaluation for a stochastic-flow network
Cites Work
- The quickest path problem
- Algorithms for the quickest path problem and the enumeration of quickest paths
- An algorithm for finding the \(k\) quickest paths in a network
- Shortest-path algorithms: Taxonomy and annotation
- An efficient algorithm for K shortest simple paths
- Fibonacci heaps and their uses in improved network optimization algorithms
- Finding the K Shortest Loopless Paths in a Network
This page was built for publication: Finding the \(k\) quickest simple paths in a network
