The multi-multiway cut problem

DOI10.1016/J.TCS.2007.02.026zbMATH Open1115.68171OpenAlexW2041499697MaRDI QIDQ884458FDOQ884458

Authors: Adi Avidor, Michael Langberg 

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

Recommendations

• Algorithm Theory - SWAT 2004
• scientific article; zbMATH DE number 1775387
• An improved approximation algorithm of MULTIWAY CUT.
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Multiway cuts in node weighted graphs

zbMATH Keywords

linear programmingapproximation algorithmsminimum multicutminimum multiway cut

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (19)

• A modeling and computational study of the frustration index in signed networks
• Algorithm Theory - SWAT 2004
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Compression via matroids: a randomized polynomial kernel for odd cycle transversal
• Nonlinear formulations and improved randomized approximation algorithms for multicut problems
• Parameterized complexity dichotomy for \textsc{Steiner Multicut}
• Generalized \(k\)-multiway cut problems
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Approximation and hardness results for the maximum edges in transitive closure problem
• Approximation algorithms for requirement cut on graphs
• \(\ell_p\)-norm multiway cut
• An improved approximation algorithm for requirement cut
• Colourful components in \(k\)-caterpillars and planar graphs
• Approximating Requirement Cut via a Configuration LP
• Separator-based data reduction for signed graph balancing
• Quasipolynomial Multicut-mimicking Networks and Kernels for Multiway Cut Problems
• A literature review on correlation clustering: cross-disciplinary taxonomy with bibliometric analysis
• The critical node detection problem in networks: a survey
• Multiway cuts in node weighted graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q884458)