A polynomial-time algorithm for computing bound sets
2006 (English)In: IEE Proceedings - Circuits Devices and Systems, ISSN 1350-2409, E-ISSN 1359-7000, Vol. 153, no 2, 179-184 p.Article in journal (Refereed) Published
An algorithm for computing bound sets of a Boolean function on its circuit representation is presented. The identification of bound sets is useful for many applications in logic synthesis, formal verification and testing. The presented algorithm computes bound sets by analysing dominator relations of the circuit. It has O(e . log n) worst-case complexity, where e is the number of edges and n is the number of vertices of the circuit graph. The experimental results show that the algorithm is efficient for large functions and allows computing bound sets for cases that were not possible to handle with previous methods.
Place, publisher, year, edition, pages
2006. Vol. 153, no 2, 179-184 p.
Algorithms, Computational complexity, Formal logic, Graph theory, Networks (circuits), Set theory
IdentifiersURN: urn:nbn:se:kth:diva-6856DOI: 10.1049/ip-cds:20041261ISI: 000237555600015ScopusID: 2-s2.0-33645000726OAI: oai:DiVA.org:kth-6856DiVA: diva2:11680
QC 20100927. Uppdaterad från Manuskript till Artikel (20100927).
QC 201507272007-03-012007-03-012015-07-27Bibliographically approved