Machine-based methods in parameterized complexity theory

DOI10.1016/j.tcs.2005.02.003zbMath1142.68032OpenAlexW2033042995MaRDI QIDQ557897

Martin Grohe, Jörg Flum, Yijia Chen

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)

Related Items (14)

Bounded fixed-parameter tractability and reducibility ⋮ Unnamed Item ⋮ Parameterized Derandomization ⋮ Parameterised counting in logspace ⋮ Unnamed Item ⋮ Parameterized random complexity ⋮ Parameterized complexity of three edge contraction problems with degree constraints ⋮ The parameterized complexity of maximality and minimality problems ⋮ W-hierarchies defined by symmetric gates ⋮ The parameterized complexity of editing graphs for bounded degeneracy ⋮ Unnamed Item ⋮ The complexity of tree partitioning ⋮ On Covering Segments with Unit Intervals ⋮ Set graphs. III: Proof pearl: Claw-free graphs mirrored into transitive hereditarily finite sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized circuit complexity and the \(W\) hierarchy
• Threshold dominating sets and an improved characterization of \(W[2\)]
• On the complexity of database queries
• On the structure of parameterized problems in NP
• Fixed-Parameter Tractability, Definability, and Model-Checking
• Computer Science Logic
• Model-Checking Problems as a Basis for Parameterized Intractability

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