Multicuts and integral multiflows in rings

We show how to solve in polynomial time the multicut and the maximum integral multiflow problems in rings. Moreover, we give linear-time procedures to solve both problems in rings with uniform capacities.

MoreLess

Year of publication:	2009
Authors:	Bentz, Cédric ; Costa, Marie-Christine ; Létocart, Lucas ; Roupin, Frédéric
Published in:	European Journal of Operational Research. - Elsevier, ISSN 0377-2217. - Vol. 196.2009, 3, p. 1251-1254
Publisher:	Elsevier
Keywords:	Combinatorial optimization Maximum integral multiflow Multicut Ring networks

More details

Type of publication:	Article
Source:	RePEc - Research Papers in Economics

Persistent link: https://ebvufind01.dmz1.zbw.eu/10005347814