DOI10.1145/301250.301430zbMath1345.90095arXivcs/0205051OpenAlexW1981960292MaRDI QIDQ2819596
Neal E. Young, Mikkel Thorup, Philip N. Klein, Clifford Stein, David R. Karger
Publication date: 29 September 2016
Published in: Mathematics of Operations Research, Proceedings of the thirty-first annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cs/0205051
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,
Experimental evaluation of a local search approximation algorithm for the multiway cut 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,
On generalized greedy splitting algorithms for multiway partition problems,
Approximation algorithms for requirement cut on graphs,
Designing FPT Algorithms for Cut Problems Using Randomized Contractions,
An improved parameterized algorithm for the minimum node multiway cut problem,
Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems,
Parameterized algorithms for min-max multiway cut and list digraph homomorphism,
\(\ell_p\)-norm multiway cut,
Global and fixed-terminal cuts in digraphs,
Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem,
Clique Cover and Graph Separation,
The multi-multiway cut problem,
Algorithms for Multiterminal Cuts,
Approximation algorithms for \(k\)-hurdle problems,
A local search approximation algorithm for the multiway cut problem,
Approximation and hardness results for label cut and related problems,
An approximation algorithm for the generalized \(k\)-multicut problem,
Strategic multiway cut and multicut games,
A tight \(\sqrt{2} \)-approximation for linear 3-cut,
On the generalized multiway cut in trees problem,
Geometric multicut: shortest fences for separating groups of objects in the plane,
Generating partitions of a graph into a fixed number of minimum weight cuts,
New geometry-inspired relaxations and algorithms for the metric Steiner tree problem,
Approximation Algorithms for CSPs,
Cut problems in graphs with a budget constraint,
Multi-Budgeted Directed Cuts,
Algorithmic aspects of homophyly of networks,
Fixed-parameter algorithms for DAG partitioning,
Submodular Cost Allocation Problem and Applications,
Approximating Requirement Cut via a Configuration LP,
Improved approximation algorithms for the maximum happy vertices and edges problems,
Optimal 3-terminal cuts and linear programming,
Greedy splitting algorithms for approximating multiway partition problems,
Minimal multicut and maximal integer multiflow: a survey,
Unnamed Item,
Simple and improved parameterized algorithms for multiterminal cuts,
Generalized \(k\)-multiway cut problems,
Approximation Algorithms for k-Hurdle Problems,
A simple algorithm for the multiway cut problem,
Improving the integrality gap for multiway cut,
Beating the 2-approximation factor for global bicut,
Simplex Transformations and the Multiway Cut Problem,
Approximation algorithms for vertex happiness,
Isolation branching: a branch and bound algorithm for the \(k \)-terminal cut problem,
On a bidirected relaxation for the MULTIWAY CUT problem,
Multi-budgeted directed cuts,
Clustering with qualitative information,
On Computing the Maximum Parsimony Score of a Phylogenetic Network,
Unnamed Item,
Unnamed Item
