Generalized Dynamic Flow on Lossy Network

  • Santosh Gautam Central Department of Mathematics, Tribhuvan University, Kathmandu
  • Urmila Pyakurel Central Department of Mathematics, Tribhuvan University, Kathmandu
  • Tanka Nath Dhamala Central Department of Mathematics, Tribhuvan University, Kathmandu
Keywords: approximation scheme, Generalized flow, lossy network, dynamic contraflow

Abstract

Despite of implicit flow conservation on every arc of traditional network flow model, the generalized network flow model assumes the proportional and symmetric loss factor on each arc. This paper considers two terminal lossy networks specifying the portion of flow entering an arc at its tail node that reaches to its head node. We studied the generalized maximum continuous dynamic contraflow (GMCDCF) and generalized continuous earliest arrival contraflow (GCEACF) problems. The problems are efficiently solved with pseudo-polynomial time algorithms. Moreover, a fully polynomial time approximation scheme (FPTAS) is proposed in polynomial time.

Downloads

Download data is not yet available.
Abstract
352
pdf
186
Published
2019-07-31
How to Cite
Gautam, S., Pyakurel, U., & Dhamala, T. (2019). Generalized Dynamic Flow on Lossy Network. Journal of the Institute of Engineering, 15(2), 171-182. https://doi.org/10.3126/jie.v15i2.27664
Section
Articles