Parameterized Approximability of the Disjoint Cycle Problem

DOI10.1007/978-3-540-73420-8_33zbMath1171.68869OpenAlexW1481813913MaRDI QIDQ5428823

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

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

Related Items

Packing arc-disjoint cycles in tournaments ⋮ Evaluation and Enumeration Problems for Regular Path Queries ⋮ Parameterized approximation via fidelity preserving transformations ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Finding a subdivision of a digraph ⋮ Parameterized approximation of dominating set problems ⋮ Kernels for packing and covering problems ⋮ Packing Cycles Faster Than Erdos--Posa ⋮ Almost 2-SAT is fixed-parameter tractable ⋮ Euler Digraphs