scientific article

zbMath0821.90125MaRDI QIDQ4035360

William H. Cunningham

Publication date: 18 May 1993

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

polyhedroncutting planeNP-completeundirected graphmaximal flowoptimal \(k\)-terminal cut

Mathematics Subject Classification ID

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

Related Items (25)

Parameterized graph separation problems ⋮ 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 ⋮ On generalized greedy splitting algorithms for multiway partition problems ⋮ Approximation algorithms for treewidth ⋮ An improved parameterized algorithm for the minimum node multiway cut problem ⋮ Extended formulations for the \(A\)-cut problem ⋮ A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms ⋮ The planar multiterminal cut problem ⋮ Nonlinear formulations and improved randomized approximation algorithms for multicut problems ⋮ Fission: Practical algorithms for computing minimum balanced node separators ⋮ An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem ⋮ The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut ⋮ Multiway cuts in directed and node weighted graphs ⋮ Optimal cuts in graphs and statistical mechanics ⋮ Optimal 3-terminal cuts and linear programming ⋮ A sufficiently fast algorithm for finding close to optimal clique trees ⋮ Minimal multicut and maximal integer multiflow: a survey ⋮ Solution methods for the vertex variant of the network system vulnerability analysis problem ⋮ Inequity aversion pricing over social networks: approximation algorithms and hardness results ⋮ On the complexity of finding balanced oneway cuts ⋮ Minimum multiway cuts in trees ⋮ An improved approximation algorithm of MULTIWAY CUT. ⋮ Multiway cut and integer flow problems in trees

This page was built for publication: