scientific article; zbMATH DE number 176254

zbMATH Open0821.90125MaRDI QIDQ4035360FDOQ4035360

Authors: William H. Cunningham 

Publication date: 18 May 1993

Title of this publication is not available (Why is that?)

Recommendations

• The Complexity of Multiterminal Cuts
• Optimal 3-terminal cuts and linear programming
• On the 3-Terminal Cut Polyhedron
• Algorithms for Multiterminal Cuts
• The planar multiterminal cut problem

zbMATH Keywords

polyhedronNP-completeundirected graphcutting planemaximal flowoptimal \(k\)-terminal cut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Connectivity (05C40)

Cited In (37)

• An optimization problem on graphs
• The multi-terminal vertex separator problem: branch-and-cut-and-price
• Optimal cuts in graphs and statistical mechanics
• On the complexity of finding balanced oneway cuts
• Algorithms for Multiterminal Cuts
• The planar multiterminal cut problem
• Minimal multicut and maximal integer multiflow: a survey
• A sufficiently fast algorithm for finding close to optimal clique trees
• Parameterized graph separation problems
• Minimum multiway cuts in trees
• The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut
• Approximation algorithms for treewidth
• On the (near) optimality of extended formulations for multi-way cut in social networks
• Nonlinear formulations and improved randomized approximation algorithms for multicut problems
• Multicriteria global minimum cuts
• On weighted multiway cuts in trees
• Generalized \(k\)-multiway cut problems
• Multiway cuts in directed and node weighted graphs
• Extended formulations for the \(A\)-cut problem
• Inequity aversion pricing over social networks: approximation algorithms and hardness results
• An improved approximation algorithm of MULTIWAY CUT.
• Experimental and Efficient Algorithms
• Solution methods for the vertex variant of the network system vulnerability analysis problem
• A lower bound of \(8/(7+\frac{1}{k-1})\) on the integrality ratio of the Călinescu-Karloff-Rabani relaxation for multiway cut
• Optimal 3-terminal cuts and linear programming
• Crossing properties of multiterminal cuts
• A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms
• Ordered optimal solutions and parametric minimum cut problems
• The maximum integer multiterminal flow problem in directed graphs
• An algorithm for computing maximum solution bases
• An improved parameterized algorithm for the minimum node multiway cut problem
• An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem
• Algorithms and Computation
• Fission: Practical algorithms for computing minimum balanced node separators
• Multiway cut and integer flow problems in trees
• On generalized greedy splitting algorithms for multiway partition problems
• Solution Bases of Multiterminal Cut Problems

This page was built for publication:

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