scientific article; zbMATH DE number 176254

MaRDI QIDQ4035360zbMATH OpenFDO

Authors William H. Cunningham

Publication date 18 May 1993

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)

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

Cited in

(40)

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