ALGORITHMS FOR THE CONSTRAINED QUICKEST PATH PROBLEM AND THE ENUMERATION OF QUICKEST PATHS

被引：92
作者：
CHEN, GH
HUNG, YC
机构：
[1] Department of Computer Science and Information Engineering, National Taiwan University, Taipei
来源：
COMPUTERS & OPERATIONS RESEARCH | 1994年 / 21卷 / 02期
关键词：
Combinatorial mathematics - Computational complexity - Constraint theory - Data communication systems - Operations research - Optimization - Sequential switching - Telecommunication networks;
D O I：
10.1016/0305-0548(94)90045-0
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
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(mn(2)) time algorithm is first presented to find constrained quickest paths, and then an O(k(2)mn(2)) time algorithm is presented to enumerate-the first k quickest paths. Our results improve previous results by Rosen, Sun and Xue.
引用
收藏
页码：113 / 118
页数：6
相关论文
共 10 条
[1]   MINIMUM COST-RELIABILITY RATIO PATH PROBLEM [J].
AHUJA, RK .
COMPUTERS & OPERATIONS RESEARCH, 1988, 15 (01) :83-89
[2]  
BODIN L, 1983, COMPUT OPER RES, V10, P63, DOI 10.1016/0305-0548(83)90030-8
[3]   THE QUICKEST PATH PROBLEM [J].
CHEN, YL ;
CHIN, YH .
COMPUTERS & OPERATIONS RESEARCH, 1990, 17 (02) :153-161
[4]   SHORTEST-PATH ALGORITHMS - TAXONOMY AND ANNOTATION [J].
DEO, N ;
PANG, CY .
NETWORKS, 1984, 14 (02) :275-323
[5]   FIBONACCI HEAPS AND THEIR USES IN IMPROVED NETWORK OPTIMIZATION ALGORITHMS [J].
FREDMAN, ML ;
TARJAN, RE .
JOURNAL OF THE ACM, 1987, 34 (03) :596-615
[6]   DETERMINISTIC NETWORK OPTIMIZATION - BIBLIOGRAPHY [J].
GOLDEN, BL ;
MAGNANTI, TL .
NETWORKS, 1977, 7 (02) :149-183
[7]   DISTRIBUTED ALGORITHMS FOR THE QUICKEST PATH PROBLEM [J].
HUNG, YC ;
CHEN, GH .
PARALLEL COMPUTING, 1992, 18 (07) :823-834
[8]  
HUNG YC, 1991, LECTURE NOTES COMPUT, P44
[9]  
Pierce A. R., 1975, Networks, V5, P129
[10]   ALGORITHMS FOR THE QUICKEST PATH PROBLEM AND THE ENUMERATION OF QUICKEST PATHS [J].
ROSEN, JB ;
SUN, SZ ;
XUE, GL .
COMPUTERS & OPERATIONS RESEARCH, 1991, 18 (06) :579-584
1