|
|||||
|
|
Multicuts and integral multiflows in rings |
|
| Authors: | Cédric Bentz Marie-Christine Costa Lucas Létocart Frédéric Roupin |
| Institution: | 1. LRI, Université Paris-Sud and CNRS, 91405 Orsay, France;2. CEDRIC, CNAM, 292 Rue St-Martin, 75141 Paris Cedex 03, France;3. LIPN, UMR CNRS 7030, Université Paris 13, 99 av. J.B. Clément, 93430 Villetaneuse, France |
| Abstract: | 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. |
| Keywords: | Combinatorial optimization Maximum integral multiflow Multicut Ring networks |
| 本文献已被 ScienceDirect 等数据库收录！ | |