Global and fixed-terminal cuts in digraphs

DOI10.4230/LIPIcs.APPROX-RANDOM.2017.2zbMath1467.68134arXiv1612.00156MaRDI QIDQ5002602

Kristóf Bérczi, Euiwoong Lee, Chao Xu, Karthekeyan Chandrasekaran, Tamás Király

Publication date: 28 July 2021

Full work available at URL: https://arxiv.org/abs/1612.00156

zbMATH Keywords

directed graphshardness of approximationarborescencegraph cuts

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)

Related Items

A tight \(\sqrt{2} \)-approximation for linear 3-cut

Cites Work

• Unnamed Item
• Blocking optimal arborescences
• Finding minimum 3-way cuts in hypergraphs
• On shredders and vertex connectivity augmentation
• An improved approximation algorithm of MULTIWAY CUT.
• Greedy splitting algorithms for approximating multiway partition problems
• Computing minimum multiway cuts in hypergraphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Complexity of approximating bounded variants of optimization problems
• Gaussian bounds for noise correlation of functions
• An improved integrality gap for the Călinescu-Karloff-Rabani relaxation for multiway cut
• Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
• Optimal 3-terminal cuts and linear programming
• A 2-Approximation Algorithm for the Directed Multiway Cut Problem
• Fault-Tolerant Consensus in Directed Graphs
• Derandomization through approximation
• Rounding algorithms for a geometric embedding of minimum multiway cut
• Augmenting Undirected Node-Connectivity by One
• On the number of shredders
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• The Complexity of Multiterminal Cuts
• A new approach to the minimum cut problem
• Simple and Fast Rounding Algorithms for Directed and Node-weighted Multiway Cut
• Approximating Multicut and the Demand Graph
• Multiway cuts in node weighted graphs
• Fast Algorithms for k-Shredders and k-Node Connectivity Augmentation
• Multiway cut, pairwise realizable distributions, and descending thresholds