Multiway cut and integer flow problems in trees

DOI10.1016/j.endm.2004.03.016zbMath1152.90353OpenAlexW2044468224MaRDI QIDQ3439138

Marie-Christine Costa, Alain Billionnet

Publication date: 29 May 2007

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2004.03.016

zbMATH Keywords

treemultiway cutmultiterminal cutmultiway flow

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Graph theory (05C99)

Related Items (6)

The maximum integer multiterminal flow problem in directed graphs ⋮ Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability ⋮ Improved parameterized and exact algorithms for cut problems on trees ⋮ An approximation algorithm for the generalized \(k\)-multicut problem ⋮ On the generalized multiway cut in trees problem ⋮ Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth

Cites Work

• Unnamed Item
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Minimal multicut and maximal integer multiflow: a survey
• On weighted multiway cuts in trees
• A greedy algorithm for multicut and integral multiflow in rooted trees
• On the multiway cut polyhedron
• Analysis of LP relaxations for multiway and multicut problems
• The Complexity of Multiterminal Cuts
• Multiway cuts in node weighted graphs

This page was built for publication: Multiway cut and integer flow problems in trees