The parameterized complexity of maximality and minimality problems

DOI10.1016/j.apal.2007.09.003zbMath1138.03034OpenAlexW1990604066MaRDI QIDQ2470035

Yijia Chen, Jörg Flum

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

zbMATH Keywords

parameterized complexityFagin-definabilitymaximality problemsminimality problems

Mathematics Subject Classification ID

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