On relation between non-disjoint decomposition and multiple-vertex dominators
2004 (English)In: 2004 IEEE INTERNATIONAL SYMPOSIUM ON CIRCUITS AND SYSTEMS, VOL 4, PROCEEDINGS, IEEE , 2004, 493-496 p.Conference paper (Refereed)
This paper addresses the problem of non-disjoint decomposition of Boolean functions. Decomposition has multiple applications in logic synthesis, testing and formal verification. First, we show that the problem of computing non-disjoint decompositions of Boolean functions can be reduced to the problem of finding multiple-vertex dominators of circuit graphs. Then, we prove that there exists an algorithm for computing all multiple-vertex dominators of a fixed size in polynomial time. Our result is important because no polynomial-time algorithm for non-disjoint decomposition of Boolean functions is known. A set of experiments on benchmark circuits illustrates our approach.
Place, publisher, year, edition, pages
IEEE , 2004. 493-496 p.
, Proceedings - IEEE International Symposium on Circuits and Systems, ISSN 0271-4310
Algorithms, Graph theory, Optimization, Polynomials, Set theory, Theorem proving
IdentifiersURN: urn:nbn:se:kth:diva-24440ISI: 000223102600124ScopusID: 2-s2.0-4344605050ISBN: 0-7803-8251-XOAI: oai:DiVA.org:kth-24440DiVA: diva2:349900
2004 IEEE International Symposium on Cirquits and Systems, Vancouver, BC; Canada; 23 May 2004 through 26 May 2004
QC 201009092010-09-092010-09-092014-12-15Bibliographically approved