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

Decomposability of partially defined Boolean functions

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

Research output: Contribution to journal › Article › peer-review

30 Scopus citations

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.

Original language	English (US)
Pages (from-to)	51-75
Number of pages	25
Journal	Discrete Applied Mathematics
Volume	62
Issue number	1-3
DOIs	https://doi.org/10.1016/0166-218X(94)00145-4
State	Published - Sep 8 1995

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

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

Cite this

@article{e27320b814a949d2a77664b904569dbb,

title = "Decomposability of partially defined Boolean functions",

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.",

author = "Endre Boros and Vladimir Gurvich and Hammer, \{Peter L.\} and Toshihide Ibaraki and Alexander Kogan",

note = "Funding Information: *Research supported in part by the Office of Naval Research (Grants NOO01492F1375 and Funding Information: NOO01492F4083) and by the Air Force Office of Scientific Research (Grant F49620-93-l-0041). *Corresponding author. E-mail: hammer@rutcor. rutgers. edu. 1O n leave from the International Institute of Earthquake Prediction Theory and Mathematical physics, Moscow, Russia.",

year = "1995",

month = sep,

day = "8",

doi = "10.1016/0166-218X(94)00145-4",

language = "English (US)",

volume = "62",

pages = "51--75",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - Decomposability of partially defined Boolean functions

AU - Boros, Endre

AU - Gurvich, Vladimir

AU - Hammer, Peter L.

AU - Ibaraki, Toshihide

AU - Kogan, Alexander

N1 - Funding Information: *Research supported in part by the Office of Naval Research (Grants NOO01492F1375 and Funding Information: NOO01492F4083) and by the Air Force Office of Scientific Research (Grant F49620-93-l-0041). *Corresponding author. E-mail: hammer@rutcor. rutgers. edu. 1O n leave from the International Institute of Earthquake Prediction Theory and Mathematical physics, Moscow, Russia.

PY - 1995/9/8

Y1 - 1995/9/8

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0002167830

UR - https://www.scopus.com/pages/publications/0002167830#tab=citedBy

U2 - 10.1016/0166-218X(94)00145-4

DO - 10.1016/0166-218X(94)00145-4

M3 - Article

AN - SCOPUS:0002167830

SN - 0166-218X

VL - 62

SP - 51

EP - 75

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-3

ER -

Decomposability of partially defined Boolean functions

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this