Bounded fixed-parameter tractability and reducibility

DOI10.1016/j.apal.2007.06.001zbMath1149.03031OpenAlexW2094650442MaRDI QIDQ2382273

Martin Grohe, Mark Weyer, Jörg Flum, Rodney G. Downey

Publication date: 28 September 2007

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2007.06.001

zbMATH Keywords

reductionsparameterized complexity theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

A Basic Parameterized Complexity Primer

Cites Work

• Unnamed Item
• Unnamed Item
• Machine-based methods in parameterized complexity theory
• On fixed-parameter tractability and approximability of NP optimization problems
• The complexity of first-order and monadic second-order logic revisited
• Graph minors. XIII: The disjoint paths problem
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• Parametrized complexity theory.
• On the structure of parameterized problems in NP
• Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
• Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
• On the Amount of Nondeterminism and the Power of Verifying
• Parameterized and Exact Computation

This page was built for publication: Bounded fixed-parameter tractability and reducibility