The parameterized complexity of maximality and minimality problems

DOI10.1016/J.APAL.2007.09.003MaRDI QIDQ2470035zbMATH OpenOpenAlexFDO

Authors 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

Fagin-definabilitymaximality problemsminimality problemsparameterized complexity

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Descriptive complexity and finite models (68Q19) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The Parameterized Complexity of Maximality and Minimality Problems
• Complexity and approximability of parameterized MAX-CSPs
• Complexity and Approximability of Parameterized MAX-CSPs
• Parameterized complexity and kernelizability of max ones and exact ones problems
• Parameterized complexity and kernelizability of Max Ones and Exact Ones problems
• The parameterized complexity of some minimum label problems
• The parameterized complexity of some minimum label problems
• scientific article; zbMATH DE number 895368
• Fixed-Parameter Complexity of Minimum Profile Problems

Cites work

• A note on the complexity of the chromatic number problem
• Algorithms and Computation
• Algorithms in the W-hierarchy
• All maximal independent sets and dynamic dominance for sparse graphs
• Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
• Describing parameterized complexity classes
• Enumerating maximal independent sets with applications to graph colouring.
• Fixed-parameter tractability, definability, and model-checking
• scientific article; zbMATH DE number 125608 (Why is no real title available?)
• scientific article; zbMATH DE number 1114020 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1979521 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Machine-based methods in parameterized complexity theory
• Parameterized complexity of finding subgraphs with hereditary properties.
• Parametrized complexity theory.
• Small Maximal Independent Sets and Faster Exact Graph Coloring
• The Parameterized Complexity of Counting Problems
• The Parameterized Complexity of Maximality and Minimality Problems

Cited in

(24)

• On parameterized complexity of the multi-MCS problem
• More complicated questions about maxima and minima, and some closures of NP
• The complexity of selecting maximal solutions
• Parameterized random complexity
• (In)approximability of maximum minimal FVS
• Minimization problems for parity OBDDs
• On the parameterized complexity of the Maximum Exposure Problem
• Parameterized complexity of computing maximum minimal blocking and hitting sets
• Parameterized bounded-depth Frege is not optimal
• HYPER-MINIMIZATION IN O(n²)
• The Parameterized Complexity of Maximality and Minimality Problems
• Parameterized Derandomization
• Fixed-parameter Approximability of Boolean MinCSPs
• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
• Dörfler marking with minimal cardinality is a linear complexity problem
• The Worst Case Complexity of Maximum Parsimony
• Parameterized and Exact Computation
• Parameterized and Exact Computation
• Complexity and Approximability of Parameterized MAX-CSPs
• The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number
• Parameterized complexity of DPLL search procedures
• On miniaturized problems in parameterized complexity theory
• Complexity of problem \(TF2|v=1,c=2|C_{\max}\)
• W-hierarchies defined by symmetric gates

This page was built for publication: The parameterized complexity of maximality and minimality problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2470035)