Factoring and recognition of read-once functions using cographs and normality
Martin Charles Golumbic, Aviad Mintz, Udi Rotics · 2001
An approach for factoring general boolean functions was described in GM:99 which is based on graph partitioning algorithms. In this paper, we present a very fast algorithm for recognizing and factoring read-once functions which is needed as a dedicated factoring subroutine to handle the lower levels of that factoring process. The algorithm is based on algorithms for cograph recognition and on checking normality. Our method has been implemented in the SIS environment, and an empirical evaluation is given.