The parameterized complexity of maximality and minimality problems
From MaRDI portal
Publication:2470035
DOI10.1016/j.apal.2007.09.003zbMath1138.03034OpenAlexW1990604066MaRDI QIDQ2470035
Publication date: 13 February 2008
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.apal.2007.09.003
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Descriptive complexity and finite models (68Q19)
Related Items
Parameterized Derandomization, Parameterized random complexity, Parameterized Bounded-Depth Frege Is Not Optimal, W-hierarchies defined by symmetric gates, Parameterized Complexity of DPLL Search Procedures
Cites Work
- Machine-based methods in parameterized complexity theory
- Enumerating maximal independent sets with applications to graph colouring.
- A note on the complexity of the chromatic number problem
- Parameterized complexity of finding subgraphs with hereditary properties.
- Describing parameterized complexity classes
- Algorithms in the W-hierarchy
- Parametrized complexity theory.
- Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
- Fixed-Parameter Tractability, Definability, and Model-Checking
- The Parameterized Complexity of Maximality and Minimality Problems
- Small Maximal Independent Sets and Faster Exact Graph Coloring
- The Parameterized Complexity of Counting Problems
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- Algorithms and Computation
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item