Parameterized circuit complexity and the \(W\) hierarchy
From MaRDI portal
Publication:1127315
DOI10.1016/S0304-3975(96)00317-9zbMath0896.68057OpenAlexW1997639167MaRDI QIDQ1127315
Michael R. Fellows, Kenneth W. Regan, Rodney G. Downey
Publication date: 13 August 1998
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(96)00317-9
Related Items
The complexity of first-order and monadic second-order logic revisited ⋮ Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues] ⋮ The Birth and Early Years of Parameterized Complexity ⋮ A Basic Parameterized Complexity Primer ⋮ Effective computation of immersion obstructions for unions of graph classes ⋮ Parameterized Derandomization ⋮ The challenges of unbounded treewidth in parameterised subgraph counting problems ⋮ On the partial vertex cover problem in bipartite graphs -- a parameterized perspective ⋮ Parameterized random complexity ⋮ Surfing with Rod ⋮ Confronting intractability via parameters ⋮ The parameterized complexity of probability amplification ⋮ Machine-based methods in parameterized complexity theory ⋮ Unnamed Item ⋮ Threshold dominating sets and an improved characterization of \(W[2\)]
Cites Work
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Matrix multiplication via arithmetic progressions
- NP is as easy as detecting unique solutions
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
- Sparse parameterized problems
- Beyond NP-completeness for problems of bounded width (extended abstract)
- PP is as Hard as the Polynomial-Time Hierarchy
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
