A greedy algorithm for multicut and integral multiflow in rooted trees |
| |
Authors: | Marie-Christine Costa,Lucas Lé tocart |
| |
Affiliation: | a CEDRIC, CNAM, 292 rue St-Martin 75141, Paris Cedex 03, France b CEDRIC, CNAM-IIE, 18 allée Jean Rostand 91025, Evry Cedex, France |
| |
Abstract: | We present an O(min(Kn,n2)) algorithm to solve the maximum integral multiflow and minimum multicut problems in rooted trees, where K is the number of commodities and n is the number of vertices. These problems are NP-hard in undirected trees but polynomial in directed trees. In the algorithm we propose, we first use a greedy procedure to build the multiflow then we use duality properties to obtain the multicut and prove the optimality. |
| |
Keywords: | Maximum integral multiflow Minimum multicut Duality Rooted tree |
本文献已被 ScienceDirect 等数据库收录! |
|