An improvement on the complexity of factoring read-once Boolean functions

DOI10.1016/j.dam.2008.02.011zbMath1145.94028OpenAlexW2031298013MaRDI QIDQ944714

Aviad Mintz, Udi Rotics, Martin Charles Golumbic

Publication date: 10 September 2008

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

Full work available at URL: https://doi.org/10.1016/j.dam.2008.02.011

zbMATH Keywords

cographslogicread-once functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Boolean functions (06E30) Boolean functions (94D10)

Related Items (3)

The complexity of AND-decomposition of Boolean functions ⋮ On exact blockers and anti-blockers, \(\varDelta \)-conjecture, and related problems ⋮ Recognizing read-once functions from depth-three formulas

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complement reducible graphs
• A simple linear time algorithm for cograph recognition
• On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
• Factoring Boolean functions using graph partitioning
• Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees
• A Linear Recognition Algorithm for Cographs
• Learning read-once formulas with queries
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: An improvement on the complexity of factoring read-once Boolean functions