A 2-approximation algorithm for the directed multiway cut problem
From MaRDI portal
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Approximation algorithms (68W25) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)
Recommendations
Cited in
(23)- An O( n)-approximation algorithm for directed sparsest cut
- An improved approximation algorithm of MULTIWAY CUT.
- A tight \(\sqrt{2} \)-approximation for linear 3-cut
- A simple algorithm for the multiway cut problem
- Beating the 2-approximation factor for global bicut
- An improved parameterized algorithm for the minimum node multiway cut problem
- The maximum integer multiterminal flow problem in directed graphs
- Hardness of cut problems in directed graphs
- Clique Cover and Graph Separation
- Approximation Algorithms for Steiner and Directed Multicuts
- Polynomial flow-cut gaps and hardness of directed cut problems
- Algorithms for Multiterminal Cuts
- Algorithms for 2-Route Cut Problems
- scientific article; zbMATH DE number 1775387 (Why is no real title available?)
- Simple and fast rounding algorithms for directed and node-weighted multiway cut
- Simplex partitioning via exponential clocks and the multiway-cut problem
- Simplex transformations and the multiway cut problem
- Global and fixed-terminal cuts in digraphs
- Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
- Vertex downgrading to minimize connectivity
- A lower bound on the integrality gap for minimum multicut in directed networks
- Solving directed multiway cut faster than 2ⁿ
- Simple and improved parameterized algorithms for multiterminal cuts
This page was built for publication: A 2-approximation algorithm for the directed multiway cut problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2784466)
