Constant ratio fixed-parameter approximation of the edge multicut problem
DOI10.1016/J.IPL.2009.07.016zbMATH Open1197.05149OpenAlexW2032692205MaRDI QIDQ990949FDOQ990949
Publication date: 1 September 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2009.07.016
Recommendations
- Constant Ratio Fixed-Parameter Approximation of the Edge Multicut Problem
- Fixed-parameter tractability of multicut parameterized by the size of the cutset
- Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
- Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
- Multicut Is FPT
fixed-parameter algorithmsgraph algorithmsmulticutsatisfiability problemsparameterized approximationEdge Multicut Problem
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Approximation algorithms (68W25)
Cites Work
- Correlation clustering
- Finding odd cycle transversals.
- Parametrized complexity theory.
- Parameterized Approximation Problems
- Title not available (Why is that?)
- Parameterized graph separation problems
- 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
- On the parameterized complexity of multiple-interval graph problems
- Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
- Fixed-parameter tractability and data reduction for multicut in trees
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
- Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
- Title not available (Why is that?)
- Correlation clustering in general weighted graphs
- On Parameterized Approximability
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- Algorithms for Multiterminal Cuts
- Clustering with Partial Information
- Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract)
- Chordal Deletion Is Fixed-Parameter Tractable
Cited In (8)
- Constant Ratio Fixed-Parameter Approximation of the Edge Multicut Problem
- Restricted vertex multicut on permutation graphs
- On the parameterized complexity of some optimization problems related to multiple-interval graphs
- On Weighted Graph Separation Problems and Flow Augmentation
- Confronting intractability via parameters
- Constant factor approximation for balanced cut in the PIE model
- On the parameterized complexity of finding separators with non-hereditary properties
- Parameterized approximation via fidelity preserving transformations
This page was built for publication: Constant ratio fixed-parameter approximation of the edge multicut problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q990949)
