DIMACS TR: 94-09

Decompositions of Partially Defined Boolean Functions



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

ABSTRACT

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