Constant Ratio Fixed-Parameter Approximation of the Edge Multicut Problem

DOI10.1007/978-3-642-04128-0_58MaRDI QIDQ3639279zbMATH OpenOpenAlexFDO

Authors Dániel Marx, Igor Razgon

Publication date 29 October 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-04128-0_58

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 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

Cited in

(3)

• Multicut Is FPT
• Constant factor approximation for balanced cut in the PIE model
• Constant ratio fixed-parameter approximation of the edge multicut problem

Describes a project that uses

Uses Software

• MAX-2-SAT

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 Q3639279)