DIMACS TR: 94-09

Decompositions of Partially Defined Boolean Functions

Authors: Endre Boros, Vladimir Gurvich, Peter L. Hammer, Toshihide Ibaraki, Alexander Kogan


The problem of recognizing decomposability of incompletely defined Boolean relations is considered. The results include polynomial time algorithms for certain important types of decompositions, as well as NP-completeness proofs for more complex structures.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-09.ps
DIMACS Home Page