|
 
|
[BEN07] The maximum integer multiterminal flow problem in directed graphs
Revue Internationale avec comité de lecture : Journal Operations Research Letters, vol. 35(2), pp. 195-200, 2007, (doi:10.1016/j.orl.2006.03.005)
motcle:
Résumé:
This paper deals with the algorithmic aspects of one fundamental
problem generalizing the famous maximum flow problem. This problem
arises, in particular, as a requests routing problem in networks.
Given an edge-capacitated graph and k terminal vertices, the maximum integer multiterminal flow problem (MaxIMTF) is to route the
maximum number of flow units between the terminals. We study this
problem in directed graphs and identify a key parameter,
that was not considered previously: kL, the number of lonely
terminals (a terminal is lonely if it lies on at least one
directed cycle containing no other terminal). We prove that
MaxIMTF is polynomial-time solvable when there is no
lonely terminal and NP-hard to approximate within 2-ε (for any ε > 0), even when kL=1 and k=3 (and also when kL=k=2). We also give an (2 log (kL+2))-approximation algorithm for the general case, and show that the case kL=1 and k=2 is tractable. Moreover, some
of our results for MaxIMTF extend to the well-known
associated minimum multiterminal cut problem or match previous results known for this minimization problem.
BibTeX
| @article { | |||
| BEN07, | |||
| title | = | "{The maximum integer multiterminal flow problem in directed graphs}", | |
| author | = | "C. Bentz", | |
| journal | = | "Operations Research Letters", | |
| year | = | 2007, | |
| volume | = | 35, | |
| number | = | 2, | |
| pages | = | "195-200", | |
| doi | = | "10.1016/j.orl.2006.03.005", | |
| } | |||
