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

treemultiway cutmultiterminal cutmultiway flow

Mathematics Subject Classification ID

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

Recommendations

• Publication:4636548
• 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

• scientific article; zbMATH DE number 176254 (Why is no real title available?)
• A greedy algorithm for multicut and integral multiflow in rooted trees
• Analysis of LP relaxations for multiway and multicut problems
• 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

(11)

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

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)