On the multiway cut polyhedron
From MaRDI portal
Publication:3971221
DOI10.1002/net.3230210106zbMath0746.90077OpenAlexW2031248452MaRDI QIDQ3971221
No author found.
Publication date: 25 June 1992
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.3230210106
Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Computational methods for problems pertaining to operations research and mathematical programming (90-08)
Related Items
On weighted multiway cuts in trees, On the (near) optimality of extended formulations for multi-way cut in social networks, A lower bound of \(8/(7+\frac{1}{k-1})\) on the integrality ratio of the Călinescu-Karloff-Rabani relaxation for multiway cut, Cluster analysis and mathematical programming, Extended formulations for the \(A\)-cut problem, Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability, The planar multiterminal cut problem, Nonlinear formulations and improved randomized approximation algorithms for multicut problems, The vertex \(k\)-cut problem, Improved parameterized and exact algorithms for cut problems on trees, Parameterized complexity of happy coloring problems, On integer and bilevel formulations for the \(k\)-vertex cut problem, Hardness of approximation for crossing number, An approximation algorithm for the generalized \(k\)-multicut problem, On the generalized multiway cut in trees problem, Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover, Multiway cuts in directed and node weighted graphs, Primal-dual approximation algorithms for integral flow and multicut in trees, On minimum 3-cuts and approximating k-cuts using Cut Trees, The critical node detection problem in networks: a survey, Optimal 3-terminal cuts and linear programming, Minimal multicut and maximal integer multiflow: a survey, Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth, Evolutionary trees: An integer multicommodity max-flow -- min-cut theorem, Linear Time Algorithms for Happy Vertex Coloring Problems for Trees, Cliques and clustering: A combinatorial approach, Minimum multiway cuts in trees, The node capacitated graph partitioning problem: A computational study, An improved approximation algorithm of MULTIWAY CUT., Multiway cut and integer flow problems in trees
Cites Work
