The Algorithmic Complexity of Modular Decomposition

Cor Bioch

ERIM Report Series Research in Management from Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam

Abstract: Modular decomposition is a thoroughly investigated topic in many areas such as switching theory, reliability theory, game theory and graph theory. We propose an O(mn)-algorithm for the recognition of a modular set of a monotone Boolean function f with m prime implicants and n variables. Using this result we show that the computation of the modular closure of a set can be done in time O(mn2). On the other hand, we prove that the recognition problem for general Boolean func tions is NP-complete. Moreover, we introduce the so called generalized Shannon decomposition of a Boolean functions as an efficient tool for proving theorems on Boolean function decompositions.

Keywords: Boolean functions; computational complexity; decomposition algorithm; modular decomposition; substitution decomposition (search for similar items in EconPapers)
JEL-codes: C69 M M11 R4 (search for similar items in EconPapers)
Date: 2001-06-14
References: Add references at CitEc
Citations:

Downloads: (external link)
https://repub.eur.nl/pub/99/erimrs20010614160249.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ems:eureri:99

Access Statistics for this paper

More papers in ERIM Report Series Research in Management from Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam Contact information at EDIRC.
Bibliographic data for series maintained by RePub ( this e-mail address is bad, please contact ).