Integral flow decomposition with minimum longest path length

This paper concerns the problem of decomposing a network flow into an integral path flow such that the length of the longest path is minimized. It is shown that this problem is NP-hard in the strong sense. Two approximation algorithms are proposed for the problem: the longest path elimination (LPE) algorithm and the balanced flow propagation (BFP) algorithm. We analyze the properties of both algorithms and present the results of experimental studies examining their performance and efficiency.