On the quickest path problem
From MaRDI portal
The problem of finding the all-pairs quickest path (between every pair of nodes) in an \(N\) input network is analyzed \((N=(V,A,C,L),| V|=n,| A|=m\) are numbers of nodes and arcs respectively, \(C(u,v)\) and \(L(u,v)\) are capacity and lead time respectively). An algorithm is presented to solve the problem for a given \(\sigma\) (the amount of data being transmitted). It is shown that the quickest path between any 2 nodes for a \(\sigma\) can be found in \(O(\log m)\) time, providing \(O(mn)^ 2\) preprocessing time.
Recommendations
Cites work
- Algorithms for finding paths with multiple constraints
- Bibliography on Algorithms for Shortest Path, Shortest Spanning Tree, and Related Circuit Routing Problems (1956–1974)
- Deterministic network optimization: A bibliography
- Fibonacci heaps and their uses in improved network optimization algorithms
- scientific article; zbMATH DE number 3690676 (Why is no real title available?)
- Minimum cost-reliability ratio path problem
- Shortest-path algorithms: Taxonomy and annotation
- The quickest path problem
Cited in
(54)- Time version of the shortest path problem in a stochastic-flow network
- Algorithms for the quickest path problem and the enumeration of quickest paths
- Distributed algorithms for the quickest path problem
- An algorithm for finding the \(k\) quickest paths in a network
- Finding the \(k\) quickest simple paths in a network
- An algorithm for the quickest path problem
- On the sum-max bicriterion path problem.
- The quickest path problem with batch constraints.
- Routing scheme of a multi-state computer network employing a retransmission mechanism within a time threshold
- The quickest path problem with interval lead times
- Extend the quickest path problem to the system reliability evaluation for a stochastic-flow network
- Probabilistic quickest path algorithm
- A label-setting algorithm for finding a quickest path
- An algorithm for ranking quickest simple paths
- Optimal flow and capacity allocation in multiple joint quickest paths of directed networks
- Solving the absolute 1-center problem in the quickest path case
- Reliability of spare routing via intersectional minimal paths within budget and time constraints by simulation
- Network redesign for efficient crowd flow and evacuation
- Reliability evaluation of a computer network in cloud computing environment subject to maintenance budget
- The all-pairs quickest path problem
- Calculation of minimal capacity vectors through \(k\) minimal paths under budget and time constraints
- A comprehensive survey on the quickest path problem
- A survey on models and algorithms for discrete evacuation planning network problems
- Fast data transmission and maximal dynamic flow.
- An efficient and robust design optimisation of multi-state flow network for multiple commodities using generalised reliability evaluation algorithm and edge reduction method
- System reliability assessment through p minimal paths in stochastic case with backup-routing
- Backup reliability of stochastic imperfect-node computer networks subject to packet accuracy rate and time constraints
- 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
- Estimated and accurate system reliabilities of a maintainable computer network subject to maintenance budget
- Fast and fine quickest path algorithm
- Reliable and restricted quickest path problems
- The Maximum Capacity Shortest Path Problem: Generation of Efficient Solution Sets
- A lower bound for the quickest path problem
- An efficient alternative to the exact evaluation of the quickest path flow network reliability problem
- The multichannel quickest-path problem
- scientific article; zbMATH DE number 1418034 (Why is no real title available?)
- Network reliability for multipath TCP networks with a retransmission mechanism under the time constraint
- Estimation of maintenance reliability for a cloud computing network
- A critical survey on the network optimization algorithms for evacuation planning problems
- On the computation of fast data transmissions in networks with capacities and delays
- Backup reliability assessment within tolerable packet error rate for a multi-state unreliable vertex computer network
- Reliability evaluation subject to assured accuracy rate and time for stochastic unreliable-node computer networks
- Spare routing problem with p minimal paths for time-based stochastic flow networks
- Computational Science - ICCS 2004
- Stochastic Algorithms: Foundations and Applications
- A method to evaluate routing policy through \(p\) minimal paths for stochastic case
- System reliability for quickest path problems under time threshold and budget
- Minimizing the expense transmission time from the source node to demand nodes
- Stochastic flow networks via multiple paths under time threshold and budget constraint
- A Monte Carlo-based algorithm for the quickest path flow network reliability problem
- Internet packet routing: application of a K-quickest path algorithm
- The quickest path problem
- On transmission time through \(k\) minimal paths of a capacitated-flow network
This page was built for publication: On the quickest path problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1261485)
