Path problem simplification with desired bounded lengths in acyclic networks

Abstract

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 DBL path problem. The complexity of the algorithm is O(m), where m is the number of arcs.

Keywords

Operations research / path problem with desired bounded lengths / equivalent simplification / path length model / acyclic network

References

[1] Al Nasr K., Ranjan D., Zubair M., Chen L., He J.. Solving the secondary structure matching problem in CryoEM De Novo modeling using a constrained k-shortest path graph algorithm. Computational Biology and Bioinformatics, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2014, 11(2): 419-430.

[2] András B., Péter K.. Determining the kth shortest path by the matrix method. Szigma–Mat.-Közgazdasági Folyóirat, 1977, 10(1–2): 61-67.

[3] Bodlaender H.L., Jansen B.M.P., Kratsch S.. Kernel bounds for path and cycle problems. Theoretical Computer Science, 2013, 511: 117-136.

[4] Chen Y.L., Tang W.. Finding the Kth shortest path in a time-scheduling network. Naval Research Logistics, 2005, 52: 93-102.

[5] Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.. Introduction to Algorithms, 2009, 3 Cambridge: The MIT Press.

[6] Fiala J., Kaminski M., Lidicky B., Paulusma D.. The k-in-a-path problem for claw-free graphs. Algorithmica, 2012, 62(1–2): 499-519.

[7] Fox B.L.. Calculating kth shortest paths. INFOR–Canad. J. Operational Res. and Information Processing, 1973, 11: 66-70.

[8] Fox B.L.. More on kth shortest path. Communications of ACM, 1975, 18(5): 279-279.

[9] Fox B.L.. K-th shortest paths and applications to probabilistic networks. Operations Research, 1975, 23: B263

[10] Gao S., Liu F., Duan Y.Y.. A Kth shortest path algorithm implemented with bi-directional search. Geomatics and Information Science of Wuhan University, 2008, 33(4): 418-421.

[11] Hiroshi M.. A new kth-shortest path algorithm. IEICE Trans. Inf. & Syst., 1993, 3: 388-389.

[12] Jiang M., Chen Y.K., Zhang Y.C. e.t.c.. Identification of hepatocellular carcinoma related genes with k-th shortest paths in a protein-protein interaction network. Molecular BioSystems, 2013, 9(11): 2720-2728.

[13] Kawarabayashi K.I., Kobayashi Y.. A linear time algorithm for the induced disjoint paths problem in planar graphs. Journal of Computer and System Sciences, 2012, 78(2): 670-680.

[14] Kelley J.E., Walker M.R.. Critical- path planning and scheduling. Proceedings of Eastern Joint IRE-ACM Computer Conference, 1959 160-173.

[15] Keshavarz-Kohjerdi F., Bagheri A.. An efficient parallel algorithm for the longest path problem in meshes. The Journal of Supercomputing, 2013, 65(2): 723-741.

[16] Kim S.K.. Linear-time algorithm for the length-constrained heaviest path problem in a tree with uniform edge lengths. IEICE Transactions on Information and Systems, 2013, 3: 498-501.

[17] Lari I., Ricca F., Scozzari A.. Comparing different metaheuristic approaches for the median path problem with bounded length. European Journal of Operational Research, 2008, 190(3): 587-597.

[18] Li J., Liu S.F., Ren Y.Y. e.t.c.. An improved Bellman algorithm for the kth shortest path problem. Mathematics in Practice and Theory, 2006, 36(1): 215-219.

[19] Lirov Y.. K-th shortest collision-free path planning. Applied Mathematics Letters, 1988, 1(1): 61-64.

[20] Li X.M., Qi J.X., Su Z.X.. Free float theorem and algorithm of seeking the k-th order critical path. Journal of Management Science in China, 2009, 12(2): 98-104.

[21] Pascoal M.M.B., Sedeno-Noda A.. Enumerating k best paths in length order in DAGs. European Journal of Operational Research, 2012, 221(2): 308-316.

[22] Qi J.X., Zhang L.H., Li X.M.. Properties and Applications of Time Floats in Network Planning Management, 2009, Beijing: Science Press, Inc.

[23] Wu B.Y.. A simpler and more efficient algorithm for the next-to-shortest path problem. Algorithmica, 2013, 65: 467-479.

[24] Yates J., Wang X.H., Chen N.N.. Assessing the effectiveness of k-shortest path sets in problems of network interdiction. Optimization and Engineering, 2014, 15(3): 721-749.