A simple algorithm for the multiway cut problem
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 5485510 (Why is no real title available?)
- scientific article; zbMATH DE number 1263204 (Why is no real title available?)
- scientific article; zbMATH DE number 1342124 (Why is no real title available?)
- scientific article; zbMATH DE number 2079348 (Why is no real title available?)
- scientific article; zbMATH DE number 6850401 (Why is no real title available?)
- A 2-approximation algorithm for the directed 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
- A tight bound on approximating arbitrary metrics by tree metrics
- An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
- An improved approximation algorithm of MULTIWAY CUT.
- An improved integrality gap for the Călinescu-Karloff-Rabani relaxation for multiway cut
- Approximate max-flow min-(multi)cut theorems and their applications
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Approximation algorithms for the 0-extension problem
- Beating the 2-approximation factor for global bicut
- Divide-and-conquer approximation algorithms via spreading metrics
- Expander flows, geometric embeddings and graph partitioning
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Minimum 0-extensions of graph metrics
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Multiway cut, pairwise realizable distributions, and descending thresholds
- Multiway cuts in node weighted graphs
- Simplex partitioning via exponential clocks and the multiway cut problem
- Simplex transformations and the multiway cut problem
- The Complexity of Multiterminal Cuts
- The design of approximation algorithms
- The geometry of graphs and some of its algorithmic applications
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
Cited in
(11)- Algorithms Solving the Matching Cut Problem
- scientific article; zbMATH DE number 2081031 (Why is no real title available?)
- A local search approximation algorithm for the multiway cut problem
- A branch-and-cut algorithm for the equicut problem
- Simplex transformations and the multiway cut problem
- Simplex partitioning via exponential clocks and the multiway-cut problem
- An improved approximation algorithm of MULTIWAY CUT.
- Algorithms for 2-Route Cut Problems
- A simple algorithm for the planar multiway cut problem
- Simplex transformations and the multiway cut problem
- Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
This page was built for publication: A simple algorithm for the multiway cut problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2294387)
