The Parameterized Complexity of Maximality and Minimality Problems

DOI10.1007/11847250_3MaRDI QIDQ3499721zbMATH OpenOpenAlexFDO

Authors Yijia Chen, Jörg Flum

Publication date 3 June 2008

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11847250_3

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The parameterized complexity of maximality and minimality problems
• The parameterized complexity of some minimum label problems
• Parameterized and Exact Computation
• On miniaturized problems in parameterized complexity theory
• Fixed-parameter tractability and completeness II: On completeness for W[1]

Cited in

(19)

• On parameterized complexity of the multi-MCS problem
• More complicated questions about maxima and minima, and some closures of NP
• Perfect Code is \(W[1]\)-complete
• (In)approximability of maximum minimal FVS
• Minimization problems for parity OBDDs
• The parameterized complexity of maximality and minimality problems
• Integer programming in parameterized complexity: five miniatures
• On the parameterized complexity of the Maximum Exposure Problem
• Parameterized complexity of computing maximum minimal blocking and hitting sets
• HYPER-MINIMIZATION IN O(n²)
• Fixed-parameter Approximability of Boolean MinCSPs
• On the Space Complexity of Parameterized Problems
• 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
• On miniaturized problems in parameterized complexity theory
• Complexity of problem \(TF2|v=1,c=2|C_{\max}\)

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 Q3499721)