Bounded fixed-parameter tractability and reducibility

DOI10.1016/J.APAL.2007.06.001MaRDI QIDQ2382273zbMATH OpenOpenAlexFDO

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

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 classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Parameterized and Exact Computation
• Modified parameterized complexity theory
• scientific article; zbMATH DE number 512804
• Fixed-parameter tractability, definability, and model-checking
• Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits

Cites work

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

Cited in

(7)

• Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
• scientific article; zbMATH DE number 1747699 (Why is no real title available?)
• A basic parameterized complexity primer
• Automata, Languages and Programming
• Parameterized and Exact Computation
• scientific article; zbMATH DE number 512844 (Why is no real title available?)
• Modified parameterized complexity theory

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

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