The multi-multiway cut problem

DOI10.1016/j.tcs.2007.02.026zbMath1115.68171OpenAlexW2041499697MaRDI QIDQ884458

Michael Langberg, Adi Avidor

Publication date: 6 June 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.02.026

zbMATH Keywords

linear programmingapproximation algorithmsminimum multicutminimum multiway cut

Mathematics Subject Classification ID

Linear programming (90C05) Approximation algorithms (68W25)

Related Items (12)

Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Approximation algorithms for requirement cut on graphs ⋮ Colourful components in \(k\)-caterpillars and planar graphs ⋮ Approximation and Hardness Results for the Maximum Edges in Transitive Closure Problem ⋮ Separator-based data reduction for signed graph balancing ⋮ A modeling and computational study of the frustration index in signed networks ⋮ Approximating Requirement Cut via a Configuration LP ⋮ The critical node detection problem in networks: a survey ⋮ An improved approximation algorithm for requirement cut ⋮ Algorithmic and hardness results for the colorful components problems ⋮ A literature review on correlation clustering: cross-disciplinary taxonomy with bibliometric analysis ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization, approximation, and complexity classes
• Approximating minimum feedback sets and multicuts in directed graphs
• An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
• Packing directed circuits fractionally
• Approximating directed multicuts
• On the hardness of approximating Multicut and Sparsest-Cut
• Clustering with qualitative information
• Rounding algorithms for a geometric embedding of minimum multiway cut
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Maximal Flow Through a Network
• On the power of unique 2-prover 1-round games
• O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
• The Complexity of Multiterminal Cuts
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Algorithms and Data Structures
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

This page was built for publication: The multi-multiway cut problem