Constant ratio fixed-parameter approximation of the edge multicut problem
From MaRDI portal
Publication:990949
DOI10.1016/j.ipl.2009.07.016zbMath1197.05149OpenAlexW2032692205MaRDI QIDQ990949
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
graph algorithmssatisfiability problemsfixed-parameter algorithmsmulticutparameterized approximationEdge Multicut Problem
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (6)
On the parameterized complexity of some optimization problems related to multiple-interval graphs ⋮ Parameterized approximation via fidelity preserving transformations ⋮ On Weighted Graph Separation Problems and Flow Augmentation ⋮ Restricted vertex multicut on permutation graphs ⋮ Confronting intractability via parameters ⋮ On the parameterized complexity of finding separators with non-hereditary properties
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Correlation clustering
- Finding odd cycle transversals.
- Parameterized graph separation problems
- On the parameterized complexity of multiple-interval graph problems
- On the hardness of approximating Multicut and Sparsest-Cut
- Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
- Parametrized complexity theory.
- Correlation clustering in general weighted graphs
- Fixed-parameter tractability and data reduction for multicut in trees
- Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- On Parameterized Approximability
- Parameterized Approximation Problems
- Algorithms for Multiterminal Cuts
- Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract)
- Chordal Deletion Is Fixed-Parameter Tractable
- On the power of unique 2-prover 1-round games
- Clustering with Partial Information
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
This page was built for publication: Constant ratio fixed-parameter approximation of the edge multicut problem
