A greedy algorithm for multicut and integral multiflow in rooted trees

DOI10.1016/S0167-6377(02)00184-0zbMath1013.90130MaRDI QIDQ1869999

Marie-Christine Costa, Lucas Létocart, Frédéric Roupin

Publication date: 4 May 2003

Published in: Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

dualityrooted treeminimum multicutmaximum integral multiflow

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)

Related Items

Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions ⋮ Models and methods for solving the problem of network vulnerability ⋮ Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree ⋮ Minimal multicut and maximal integer multiflow: a survey ⋮ Improved algorithms for the multicut and multiflow problems in rooted trees ⋮ Multicuts and integral multiflows in rings ⋮ Multiway cut and integer flow problems in trees

Cites Work

• Primal-dual approximation algorithms for integral flow and multicut in trees
• The Complexity of Multiterminal Cuts
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm