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

parameterized complexityFagin-definabilitymaximality problemsminimality problems

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• 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

(23)

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

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)