On the structure and the number of prime implicants of 2-\(\mathsf{CNF}\)s

DOI10.1016/j.dam.2015.06.036zbMath1330.94067arXiv1408.2662OpenAlexW212833240MaRDI QIDQ906424

Navid Talebanfard

Publication date: 21 January 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1408.2662

zbMATH Keywords

computational complexitycombinatorial problemsBoolean functionprime implicantconjunctive normal form

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (1)

Connected Boolean functions with a locally extremal number of prime implicants

Cites Work

• On the number of prime implicants
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• On converting CNF to DNF
• On k-Term DNF with the Largest Number of Prime Implicants
• An improved exponential-time algorithm for k -SAT
• On cliques in graphs

This page was built for publication: On the structure and the number of prime implicants of 2-\(\mathsf{CNF}\)s