The all-pairs quickest path problem
The quickest path problem, proposed by \textit{Y. L. Chen} and \textit{Y. N. Chin} [Comput. Oper. Res. 17, No. 2, 153-161 (1990; Zbl 0698.90083)], is defined as follows. We have a communication network \(N=(V,A,c.l)\), where \(G=(V,A)\) is a directed graph without multiple arcs and self-loops, \(c(u,v)\geq 0\) is the capacity of an arc \((u,v)\in A\), and \(l(u,v)\geq 0\) is the lead time of an arc \((u,v)\in A\). For an arc \((u,v)\), the capacity \(c(u,v)\) denotes the maximum number of data units which can be transmitted from node \(u\) to node \(v\) per unit time, and \(l(u,v)\) denotes the lead time required to send data from node \(u\) to node \(v\). If \(\sigma\geq 0\) units of data are transmitted from node \(u\) through arc \((u,v)\), then the required transmission time is \(l(u,v)+(\sigma/c(u,v))\). Let \(\rho(u_ 1,u_ 2,\dots,u_ k)\) be a path from \(u_ 1\) to \(u_ k\). Then the lead time \(l(p)\) along the path \(p\) is \(l(p)=\sum_{i=1}^{k-1} l(u_ i,u_{i+1})\) and the capacity \(c(p)\) of path \(p\) is \(c(p)=\min_{1\leq i\leq k-1} c(u_ i,u_{i+1})\). To send \(\sigma\) units of data from \(u_ 1\) to \(u_ k\) through path \(p\), the total transmission time required is \(T_ p(\sigma)=l(p)+\sigma/c(p)\). Given nodes \(s\) and \(t\), the quickest path problem is to find a path \(p\) from \(s\) to \(t\), such that the total transmission time to send \(\sigma\geq 0\) units of data from \(s\) to \(t\) is minimum among all possible paths from \(s\) to \(t\) in the network \(N\). This problem is a variant of the shortest path problem. But the optimality property of shortest paths no longer holds. That is, if \(p\) is a shortest path from \(u\) to \(v\), then any subpath of \(p\) must itself be shortest. In this paper the all-pairs quickest path problem as a function of \(\sigma\) is discussed. That is, we preprocess the network in such a way that given any pair of nodes \(u\), \(v\) and any amount of data \(\sigma\geq 0\), report the quickest path to transmit the data from \(u\) to \(v\). Throughout this paper, \(n\) will denote the number of nodes \(| V|\), \(m\) will denote the number of arcs \(| A|\), and \(r\) will denote the number of distinct capacities. The preprocessing time is \(O(mn^ 2)\) or \(O(rmn+rn^ 2\log n)\) if \(r\) is small,space is \(O(rn^ 2)\), and query time for a pair of nodes is \(O(\log r)\) plus the number of arcs of the actual path if it is to be reported.
- Algorithms for the quickest path problem and the enumeration of quickest paths
- Fibonacci heaps and their uses in improved network optimization algorithms
- scientific article; zbMATH DE number 3900809 (Why is no real title available?)
- scientific article; zbMATH DE number 3907787 (Why is no real title available?)
- scientific article; zbMATH DE number 3481857 (Why is no real title available?)
- The quickest path problem
- Time version of the shortest path problem in a stochastic-flow network
- Reliability based assignment in stochastic-flow freight network
- An algorithm for finding the \(k\) quickest paths in a network
- On the quickest path problem
- The inverse-parametric knapsack problem
- On the sum-max bicriterion path problem.
- Routing scheme of a multi-state computer network employing a retransmission mechanism within a time threshold
- Distribution and reliability evaluation of MAX-flow in dynamic multi-state flow networks
- The quickest path problem with interval lead times
- A cost-time trade-off Königsberg bridge problem traversing all the seven bridges allowing repetition
- Extend the quickest path problem to the system reliability evaluation for a stochastic-flow network
- Probabilistic quickest path algorithm
- 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
- Reliability evaluation of a computer network in cloud computing environment subject to maintenance budget
- Calculation of minimal capacity vectors through \(k\) minimal paths under budget and time constraints
- A comprehensive survey on the quickest path problem
- Fast data transmission and maximal dynamic flow.
- System reliability assessment through p minimal paths in stochastic case with backup-routing
- All pairs lightest shortest paths
- 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
- The Maximum Capacity Shortest Path Problem: Generation of Efficient Solution Sets
- An efficient alternative to the exact evaluation of the quickest path flow network reliability problem
- scientific article; zbMATH DE number 5289563 (Why is no real title available?)
- Algorithms for the quickest time distribution of dynamic stochastic-flow networks
- Estimation of maintenance reliability for a cloud computing network
- 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
- Assessment of spare reliability for multi-state computer networks within tolerable packet unreliability
- MIN-MAX quickest path problems
- Spare routing problem with p minimal paths for time-based stochastic flow networks
- Computational Science - ICCS 2004
- A method to evaluate routing policy through \(p\) minimal paths for stochastic case
- System reliability for quickest path problems under time threshold and budget
- 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
- A priority queue for the all pairs shortest path problem
- The quickest path problem
- On transmission time through \(k\) minimal paths of a capacitated-flow network
This page was built for publication: The all-pairs quickest path problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2366074)
