The parameterized complexity of maximality and minimality problems
From MaRDI portal
Publication:2470035
DOI10.1016/j.apal.2007.09.003zbMath1138.03034MaRDI 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
68Q25: Analysis of algorithms and problem complexity
03D15: Complexity of computation (including implicit computational complexity)
68Q19: Descriptive complexity and finite models
Related Items
Parameterized Complexity of DPLL Search Procedures, W-hierarchies defined by symmetric gates, Parameterized random complexity, Parameterized Bounded-Depth Frege Is Not Optimal, Parameterized Derandomization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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