DECOMPOSABILITY OF PARTIALLY DEFINED BOOLEAN FUNCTIONS

Authors
BOROS E GURVICH V HAMMER PL IBARAKI T KOGAN A
Citation
E. Boros et al., DECOMPOSABILITY OF PARTIALLY DEFINED BOOLEAN FUNCTIONS, Discrete applied mathematics, 62(1-3), 1995, pp. 51-75
Citations number
21
Categorie Soggetti
Mathematics,Mathematics
Journal title
Discrete applied mathematics → ACNP
Volume
62
Issue
1-3
Year of publication
1995
Pages
51 - 75
Database
ISI
SICI code
Abstract
The problem of recognizing decomposability of partially defined Boolea n functions is considered. The results include polynomial time algorit hms for certain important types of decomposition, as well as NP-comple teness proofs for more complex structures.