Approximate Algorithms for Continuous-Time Quickest Multi-Commodity Contraflow Problem

Authors

  • Shiva Prakash Gupta Tri-Chandra Multiple Campus, Tribhuvan University, Kathmandu
  • Durga Prasad Khanal Saraswati Multiple Campus, Tribhuvan University, Kathmandu
  • Urmila Pyakurel Central Department of Mathematics, Tribhuvan University, Kathmandu
  • Tanka Nath Dhamala Central Department of Mathematics, Tribhuvan University, Kathmandu

DOI:

https://doi.org/10.3126/nmsr.v37i1-2.34068

Keywords:

Multi-commodity flow, continuous-time, quickest contra flow, length bound, -condense

Abstract

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. 

 

Downloads

Download data is not yet available.
Abstract
211
pdf
103

Downloads

Published

2020-12-31

How to Cite

Gupta, S. P., Khanal, D. P., Pyakurel, U., & Dhamala, T. N. (2020). Approximate Algorithms for Continuous-Time Quickest Multi-Commodity Contraflow Problem. The Nepali Mathematical Sciences Report, 37(1-2), 30–46. https://doi.org/10.3126/nmsr.v37i1-2.34068

Issue

Section

Articles