On polynomial-time combinatorial algorithms for maximum L-bounded flow

Abstract

We describe a combinatorial algorithm based on the exponential length method that finds a (1+ε) -approximation of the maximum L-bounded flow. Moreover, we show that this approach works even for the NP-hard generalization of the maximum L-bounded flow problem in which each edge has a length.

Keywords

• L-bounded flow