On the fixed-parameter tractability of the equivalence test of monotone normal forms
From MaRDI portal
Publication:2379965
DOI10.1016/j.ipl.2007.03.009zbMath1184.68662OpenAlexW2011997521MaRDI QIDQ2379965
Publication date: 24 March 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2007.03.009
computational complexityanalysis of algorithmsfixed-parameter tractabilityequivalence testmonotone normal forms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
- On generating all maximal independent sets
- On the complexity of inferring functional dependencies
- Exact transversal hypergraphs and application to Boolean \(\mu\)-functions
- The complexity of minimum partial truth assignments and implication in negation-free formulae
- Monotone Boolean dualization is in co-NP\([\log^{2}n\).]
- Complexity of identification and dualization of positive Boolean functions
- An Efficient Algorithm for the Transversal Hypergraph Generation
- How to assign votes in a distributed system
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle
- The Maximum Latency and Identification of Positive Boolean Functions
- NP-completeness: A retrospective
- New Results on Monotone Dualization and Generating Hypergraph Transversals
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
This page was built for publication: On the fixed-parameter tractability of the equivalence test of monotone normal forms
