Machine-based methods in parameterized complexity theory
From MaRDI portal
Publication:557897
DOI10.1016/J.TCS.2005.02.003zbMATH Open1142.68032OpenAlexW2033042995MaRDI QIDQ557897FDOQ557897
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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]\)
- On the complexity of database queries
- Title not available (Why is that?)
- Fixed-parameter tractability, definability, and model-checking
- Title not available (Why is that?)
- Computer Science Logic
- Model-Checking Problems as a Basis for Parameterized Intractability
Cited In (24)
- W-hierarchies defined by symmetric gates
- Title not available (Why is that?)
- The parameterized complexity of maximality and minimality problems
- Parameterized Derandomization
- On Covering Segments with Unit Intervals
- Parameterised counting in logspace
- Fixed Structure Complexity
- The parameterized space complexity of model-checking bounded variable first-order logic
- Completeness results for parameterized space classes
- A Purely Democratic Characterization of W[1]
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Set graphs. III: Proof pearl: Claw-free graphs mirrored into transitive hereditarily finite sets
- Relativization and interactive proof systems in parameterized complexity theory
- Machine characterizations for parameterized complexity classes beyond para-NP
- Bounded fixed-parameter tractability and reducibility
- Parameterized complexity of three edge contraction problems with degree constraints
- The parameterized complexity of editing graphs for bounded degeneracy
- Describing parameterized complexity classes
- Parameterized random complexity
- An analysis of the W*-hierarchy
- Algorithms in the W-hierarchy
- Title not available (Why is that?)
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)
