On the fixed-parameter tractability of the equivalence test of monotone normal forms
From MaRDI portal
Publication:2379965
DOI10.1016/J.IPL.2007.03.009zbMATH Open1184.68662OpenAlexW2011997521MaRDI QIDQ2379965FDOQ2379965
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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- On the complexity of inferring functional dependencies
- How to assign votes in a distributed system
- On generating all maximal independent sets
- NP-completeness: A retrospective
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- New Results on Monotone Dualization and Generating Hypergraph Transversals
- Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
- Complexity of identification and dualization of positive Boolean functions
- Exact transversal hypergraphs and application to Boolean \(\mu\)-functions
- Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle
- The Maximum Latency and Identification of Positive Boolean Functions
- Monotone Boolean dualization is in co-NP\([\log^{2}n]\).
- An Efficient Algorithm for the Transversal Hypergraph Generation
- The complexity of minimum partial truth assignments and implication in negation-free formulae
Cited In (1)
This page was built for publication: On the fixed-parameter tractability of the equivalence test of monotone normal forms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2379965)
