Decomposability of partially defined Boolean functions

Endre Boros; Vladimir Gurvich; Peter L Hammer; Toshihide Ibaraki; Alexander Kogan

doi:10.1016/0166-218X(94)00145-4

Back

Decomposability of partially defined Boolean functions

Journal article

Open access

Peer reviewed

Decomposability of partially defined Boolean functions

Endre Boros, Vladimir Gurvich, Peter L Hammer, Toshihide Ibaraki and Alexander Kogan

Discrete Applied Mathematics, Vol.62(1), pp.51-75

1995

DOI: https://doi.org/10.1016/0166-218X(94)00145-4

Abstract

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

Files and links (1)

url

https://doi.org/10.1016/0166-218X(94)00145-4View

Version of Record (VoR) Open

Metrics

9 Record Views

21 Times Cited - Web of Science

Details

Title: Decomposability of partially defined Boolean functions
Creators: Endre Boros - RUTCOR, Rutgers University, P.O. Box 5062, New Brunswick, NJ 08903, USA
Vladimir Gurvich - RUTCOR, Rutgers University, P.O. Box 5062, New Brunswick, NJ 08903, USA
Peter L Hammer - RUTCOR, Rutgers University, P.O. Box 5062, New Brunswick, NJ 08903, USA
Toshihide Ibaraki - Department of Applied Mathematics and Physics, Faculty of Engineering, Kyoto University, Kyoto 606, Japan
Alexander Kogan - Faculty of Management and RUTCOR, Rutgers University, P.O. Box 5062, New Brunswick, NJ 08903, USA
Publication Details: Discrete Applied Mathematics, Vol.62(1), pp.51-75
Date published: 1995
Publisher: Elsevier B.V
Academic Unit: Accounting and Information Systems (RBS); Management Science and Information Systems (RBS)
Language: English
Resource Type: Journal article
Identifiers: 991031666283304646