Kołtyś, K; Pieńkosz, K
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 isNP-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.
Słowa kluczowe: Networks, Flow decomposition, Integral flow, NP-hardproblem, Approximation algorithms
Strona www: -