The parameterized complexity of maximality and minimality problems

DOI10.1016/j.apal.2007.09.003zbMath1138.03034MaRDI 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 complexity; Fagin-definability; maximality problems; minimality problems

Mathematics Subject Classification ID

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