scientific article; zbMATH DE number 176254

MaRDI QIDQ4035360zbMATH OpenFDO

Authors William H. Cunningham

Publication date 18 May 1993

zbMATH Keywords

cutting planemaximal flowNP-completeoptimal \(k\)-terminal cutpolyhedronundirected graph

Mathematics Subject Classification ID

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

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

(47)

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

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)