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

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.