Constant ratio fixed-parameter approximation of the edge multicut problem

DOI10.1016/J.IPL.2009.07.016MaRDI QIDQ990949zbMATH OpenOpenAlexFDO

Authors Dániel Marx, Igor Razgon

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

zbMATH Keywords

fixed-parameter algorithmsgraph algorithmsmulticutsatisfiability problemsparameterized approximationEdge Multicut Problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Approximation algorithms (68W25)

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

Cites work

• scientific article; zbMATH DE number 5485529 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
• Algorithms for Multiterminal Cuts
• Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract)
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Chordal Deletion Is Fixed-Parameter Tractable
• Clustering with Partial Information
• Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
• Correlation clustering
• Correlation clustering in general weighted graphs
• Finding odd cycle transversals.
• Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
• Fixed-parameter tractability and data reduction for multicut in trees
• Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
• On Parameterized Approximability
• On the hardness of approximating Multicut and Sparsest-Cut
• On the parameterized complexity of multiple-interval graph problems
• On the power of unique 2-prover 1-round games
• Parameterized Approximation Problems
• Parameterized graph separation problems
• Parametrized complexity theory.

Cited in

(8)

• Confronting intractability via parameters
• On the parameterized complexity of finding separators with non-hereditary properties
• Parameterized approximation via fidelity preserving transformations
• Restricted vertex multicut on permutation graphs
• Constant factor approximation for balanced cut in the PIE model
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• Constant Ratio Fixed-Parameter Approximation of the Edge Multicut Problem
• On Weighted Graph Separation Problems and Flow Augmentation

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)