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