Machine-based methods in parameterized complexity theory

DOI10.1016/J.TCS.2005.02.003MaRDI QIDQ557897zbMATH OpenOpenAlexFDO

Authors Yijia Chen, Jörg Flum, Martin Grohe

Publication date 30 June 2005

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2005.02.003

zbMATH Keywords

Complexity classesMachine characterizationsParameterized complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 2183396
• Parameterized random complexity
• scientific article; zbMATH DE number 1114020
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
• Computation Models for Parameterized Complexity

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 1222098 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1453052 (Why is no real title available?)
• Computer Science Logic
• Fixed-parameter tractability, definability, and model-checking
• Model-Checking Problems as a Basis for Parameterized Intractability
• On the complexity of database queries
• On the structure of parameterized problems in NP
• Parameterized circuit complexity and the \(W\) hierarchy
• Threshold dominating sets and an improved characterization of \(W[2]\)

Cited in

(24)

• Completeness results for parameterized space classes
• Bounded fixed-parameter tractability and reducibility
• scientific article; zbMATH DE number 2086399 (Why is no real title available?)
• Parameterized complexity of three edge contraction problems with degree constraints
• Algorithms in the W-hierarchy
• Describing parameterized complexity classes
• Set graphs. III: Proof pearl: Claw-free graphs mirrored into transitive hereditarily finite sets
• The parameterized complexity of maximality and minimality problems
• Parameterized Derandomization
• Relativization and interactive proof systems in parameterized complexity theory
• Machine characterizations for parameterized complexity classes beyond para-NP
• A Purely Democratic Characterization of W[1]
• The parameterized space complexity of model-checking bounded variable first-order logic
• Parameterized random complexity
• Fixed Structure Complexity
• On Covering Segments with Unit Intervals
• scientific article; zbMATH DE number 7378390 (Why is no real title available?)
• Parameterised counting in logspace
• An analysis of the W*-hierarchy
• W-hierarchies defined by symmetric gates
• The parameterized complexity of editing graphs for bounded degeneracy
• scientific article; zbMATH DE number 2183396 (Why is no real title available?)
• scientific article; zbMATH DE number 11760 (Why is no real title available?)
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues

This page was built for publication: Machine-based methods in parameterized complexity theory

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