Title: Faster approximation algorithm for generalised maximum concurrent flow problem in networks with no flow-generating cycles

Authors: Liwei Dong, Hong Wang, Xiaofen Zhang

Addresses: Department of Software, Shenyang Normal University, Shenyang, China. ' Department of Software, Shenyang Normal University, Shenyang, China. ' Department of Software, Shenyang Normal University, Shenyang, China

Abstract: This paper presents fully polynomial approximation algorithm for generalised maximum concurrent flow problem in networks with no flow-generating cycles. This paper is showed by modifying the algorithms by Fleischer and Dong. For all commodities which have a common source the new algorithm calls subroutine to find their generalised shortest paths only one time, so the running time is independent of the number of commodities k. At the same time the new algorithm applies to not only to the lossy networks but also to the networks with no flow-generating cycles.

Keywords: fully polynomial approximation algorithms; generalised maximum concurrent flows; flow-generating cycles; shortest paths; lossy networks; flow problems; services operations; services management; informatics.

DOI: 10.1504/IJSOI.2010.031046

International Journal of Services Operations and Informatics, 2010 Vol.5 No.1, pp.20 - 35

Published online: 19 Jan 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article