Generalized Dynamic Flow on Lossy Network

摘要

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.