Parameterized Approximability of the Disjoint Cycle Problem

DOI10.1007/978-3-540-73420-8_33MaRDI QIDQ5428823zbMATH OpenOpenAlexFDO

Authors Martin Grohe, Magdalena Grüber

Publication date 28 November 2007

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73420-8_33

zbMATH Keywords

approximation algorithmsfixed-parameter tractabilityparameterized complexity theory

Mathematics Subject Classification ID

Paths and cycles (05C38) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• Approximability of packing disjoint cycles
• Approximability of Packing Disjoint Cycles
• Approximation algorithms for cycle packing problems
• Approximation algorithms and hardness results for cycle packing problems
• Disjoint Cycles: Integrality Gap, Hardness, and Approximation

Cited in

(15)

• Almost 2-SAT is fixed-parameter tractable
• Parameterized approximation via fidelity preserving transformations
• On the Cycle Augmentation Problem: hardness and approximation algorithms
• Kernels for packing and covering problems
• An algorithmic answer to the Ore-type version of Dirac's question on disjoint cycles
• Packing arc-disjoint cycles in tournaments
• Euler digraphs
• Evaluation and enumeration problems for regular path queries
• Parameterized Algorithms for List K-Cycle
• Finding a subdivision of a digraph
• From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
• Packing cycles faster than Erdős-Pósa
• Approximability of Packing Disjoint Cycles
• Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond
• Parameterized approximation of dominating set problems

This page was built for publication: Parameterized Approximability of the Disjoint Cycle Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5428823)