Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
From MaRDI portal
Publication:2581756
DOI10.1016/j.jcss.2005.06.003zbMath1110.68050OpenAlexW1542263829MaRDI QIDQ2581756
Mark Weyer, Martin Grohe, Jörg Flum
Publication date: 10 January 2006
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2005.06.003
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Bounded fixed-parameter tractability and reducibility ⋮ Unnamed Item ⋮ Parameterized random complexity ⋮ Confronting intractability via parameters ⋮ Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic ⋮ The parameterized complexity of maximality and minimality problems ⋮ Slightly Superexponential Parameterized Problems ⋮ Hybridization Number on Three Rooted Binary Trees is EPT ⋮ Planar Capacitated Dominating Set Is W[1-Hard]
Cites Work
- Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete
- On the complexity of database queries
- On limited nondeterminism and the complexity of the V-C dimension
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
- Fixed-Parameter Tractability, Definability, and Model-Checking
- Query evaluation via tree-decompositions
- New results on monotone dualization and generating hypergraph transversals
- Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
- Model-Checking Problems as a Basis for Parameterized Intractability
- Parameterized and Exact Computation
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
