Multiway cut and integer flow problems in trees

DOI10.1016/J.ENDM.2004.03.016MaRDI QIDQ3439138zbMATH OpenOpenAlexFDO

Authors 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

multiterminal cutmultiway cutmultiway flowtree

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 6861995
• A greedy algorithm for multicut and integral multiflow in rooted trees
• Minimum multiway cuts in trees
• Primal-dual approximation algorithms for integral flow and multicut in trees
• On the generalized multiway cut in trees problem

Cites work

• A greedy algorithm for multicut and integral multiflow in rooted trees
• Analysis of LP relaxations for multiway and multicut problems
• scientific article; zbMATH DE number 176254 (Why is no real title available?)
• Minimal multicut and maximal integer multiflow: a survey
• Multiway cuts in node weighted graphs
• On the multiway cut polyhedron
• On weighted multiway cuts in trees
• Primal-dual approximation algorithms for integral flow and multicut in trees
• The Complexity of Multiterminal Cuts

Cited in

(12)

• Improved algorithms for the multicut and multiflow problems in rooted trees
• On weighted multiway cuts in trees
• Evolutionary trees: An integer multicommodity max-flow -- min-cut theorem
• A greedy algorithm for multicut and integral multiflow in rooted trees
• Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
• Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability
• On the generalized multiway cut in trees problem
• Multiroute flows: cut-trees and realizability
• The maximum integer multiterminal flow problem in directed graphs
• An approximation algorithm for the generalized k-multicut problem
• scientific article; zbMATH DE number 6861995 (Why is no real title available?)
• Improved parameterized and exact algorithms for cut problems on trees

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3439138)