TY - JOUR
AU - Shiva Gupta
AU - Durga Khanal
AU - Urmila Pyakurel
AU - Tanka Dhamala
PY - 2020/12/31
Y2 - 2021/03/01
TI - Approximate Algorithms for Continuous-Time Quickest Multi-Commodity Contraflow Problem
JF - The Nepali Mathematical Sciences Report
JA - nmsr
VL - 37
IS - 1-2
SE - Articles
DO - 10.3126/nmsr.v37i1-2.34068
UR - https://www.nepjol.info/index.php/nmsr/article/view/34068
AB - Multi-commodity flow problem appears when several distinct commodities are shipped from supply nodes to the demand nodes through a network without violating the capacity constraints. The quickest multi-commodity flow problem deals with the minimization of time satisfying given demand. Ingeneral, the quickest multi-commodity flow problems are computationally hard. The outbound lane capacities can be increased through reverting the orientation of lanes towards the demand nodes. We present two approximation algorithms by introducing partial contraow technique in the continuous-time quick estmulti-commodity ow problem: one polynomial-time with the help of length-bounded flow and another FPTAS by using _-condensed time-expanded graph. Both algorithms reverse only necessary arc capacities to get the optimal solutions and save unused arc capacities which may be used for other purposes.
ER -