|
 
|
[BCR07] Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs
Revue Internationale avec comité de lecture : Journal Journal of Discrete Algorithms, vol. 5(1), pp. 36-54, 2007, (doi:10.1016/j.jda.2006.03.009)
motcle:
Résumé:
In this paper, we deal with the maximum integer multiflow and the minimum multicut problems in rectilinear grid graphs with uniform capacities on the edges. The first problem is known to be NP-hard when any vertex can be a terminal, and we show that the second one is also NP-hard. Then, we study the case where the terminals are located in a two-sided way on the boundary of the outer face. We prove that, in this case, both problems are polynomial time solvable. Furthermore, we give two efficient combinatorial algorithms using a primal-dual approach. Our work is based on previous results concerning related decision problems. (The PDF file you can download contains an erratum for the proof of Lemma 21.)
Equipe:
oc
Collaboration:
LIPN
BibTeX
| @article { | |||
| BCR07, | |||
| title | = | "{Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs}", | |
| author | = | "C. Bentz and M.-C. Costa and F. Roupin", | |
| journal | = | "Journal of Discrete Algorithms", | |
| year | = | 2007, | |
| volume | = | 5, | |
| number | = | 1, | |
| pages | = | "36-54", | |
| doi | = | "10.1016/j.jda.2006.03.009", | |
| } | |||
