PATH PROBLEM SIMPLIFICATION WITH DESIRED BOUNDED LENGTHS IN ACYCLIC NETWORKS  

作　　者：Zhixiong Su Jianxun Qi Hanying Wei 

机构地区：[1]Business Administration College,Nanchang Institute of Technology [2]School of Economics and Management,North China Electric Power University

出　　处：《Journal of Systems Science and Systems Engineering》2015年第4期500-519,共20页系统科学与系统工程学报（英文版）

基　　金：Natural Science Foundation of China(No. 71171079 and 71271081);the Natural Science Foundation of Jiangxi Provincial Department of Science and Technology in China(No. 20151BAB211015);the Jiangxi Research Center of Soft Science for Water Security& Sustainable Development for financially supporting this work

摘　　要：Path determination is a fundamental problem of operations research. Current solutions mainly focus on the shortest and longest paths. We consider a more generalized problem; specifically, we consider the path problem with desired bounded lengths （DBL path problem）. This problem has extensive applications; however, this problem is much harder, especially for large-scale problems. An effective approach to this problem is equivalent simplification. We focus on simplifying the problem in acyclic networks and creating a path length model that simplifies relationships between various path lengths. Based on this model, we design polynomial algorithms to compute the shortest, longest, second shortest, and second longest paths that traverse any arc. Furthermore, we design a polynomial algorithm for the equivalent simplification of the is O（m）, where m is the number of arcs. DBL path problem. The complexity of the algorithmPath determination is a fundamental problem of operations research. Current solutions mainly focus on the shortest and longest paths. We consider a more generalized problem; specifically, we consider the path problem with desired bounded lengths （DBL path problem）. This problem has extensive applications; however, this problem is much harder, especially for large-scale problems. An effective approach to this problem is equivalent simplification. We focus on simplifying the problem in acyclic networks and creating a path length model that simplifies relationships between various path lengths. Based on this model, we design polynomial algorithms to compute the shortest, longest, second shortest, and second longest paths that traverse any arc. Furthermore, we design a polynomial algorithm for the equivalent simplification of the is O（m）, where m is the number of arcs. DBL path problem. The complexity of the algorithm

关 键 词：Operations research path problem with desired bounded lengths equivalent simplification path length model acyclic network 

分 类 号：O157.5[理学—数学]