Efficient computation of dominators in multiple-output circuit graphs
2005 (English)In: Proceedings - IEEE International Symposium on Circuits and Systems, 2005, 2223-2226 p.Conference paper (Refereed)
In this paper we present an efficient technique for computing dominators in multiple-output circuit graphs. Dominators provide information about the origin and the end of reconverging paths in a graph. This information is widely used in CAD applications such as satisfiability checking, equivalence checking, ATPG, technology mapping, decomposition of Boolean functions and power optimization. Experiments on a large set of benchmarks show a significant performance improvement of our new technique in comparison to the well-known algorithm for computing dominators in flowgraphs presented by Lengauer and Tarjan. We will demonstrate that in contrast to previous techniques our algorithm obtains performance improvements especially for large benchmarks.
Place, publisher, year, edition, pages
2005. 2223-2226 p.
, IEEE International Symposium on Circuits and Systems, ISSN 0271-4302
Boolean functions, Graphic methods
Electrical Engineering, Electronic Engineering, Information Engineering
IdentifiersURN: urn:nbn:se:kth:diva-43158DOI: 10.1109/ISCAS.2005.1465064ISI: 000232002402079ScopusID: 2-s2.0-67649122205OAI: oai:DiVA.org:kth-43158DiVA: diva2:448193
IEEE International Symposium on Circuits and Systems 2005, ISCAS 2005; Kobe; 23 May 2005 through 26 May 2005
QC 201110142011-10-142011-10-132011-10-14Bibliographically approved