Constant ratio fixed-parameter approximation of the edge multicut problem
From MaRDI portal
Publication:990949
DOI10.1016/j.ipl.2009.07.016zbMath1197.05149MaRDI 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 algorithms; satisfiability problems; fixed-parameter algorithms; multicut; parameterized approximation; Edge Multicut Problem
68Q25: Analysis of algorithms and problem complexity
05C35: Extremal problems in graph theory
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
Restricted vertex multicut on permutation graphs, Confronting intractability via parameters, On the parameterized complexity of finding separators with non-hereditary properties, On the parameterized complexity of some optimization problems related to multiple-interval graphs
Cites Work
- Unnamed Item
- 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
