Algorithms for the constrained quickest path problem and the enumeration of quickest paths.
Journal
Computers & OR
Journal Volume
21
Journal Issue
2
Pages
113-118
Date Issued
1994
Author(s)
Hung, Yung-Chen
Abstract
The quickest path problem, which was originally proposed by Chen and Chin, is a variant of the shortest path problem. Its objective is to find quickest paths in a network to transmit a given amount of data such that the transmission time is minimized. If the quickest paths are required to go through a specified path, then the restricted problem is called the constrained quickest path problem. In this paper, for all pairs of nodes in a network N, an O(mn2) time algorithm is first presented to find constrained quickest paths, and then an O(k2mn2) time algorithm is presented to enumerate the first k quickest paths. Our results improve previous results by Rosen, Sun and Xue. © 1993.
Other Subjects
Combinatorial mathematics; Computational complexity; Constraint theory; Data communication systems; Operations research; Optimization; Sequential switching; Telecommunication networks; Constrained quickest path problem; Nodes; Sequential algorithm; Shortest path problem; Time algorithm; Algorithms
Type
journal article