Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Efficient computation of dominators in multiple-output circuit graphs
KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
2005 (English)In: Proceedings - IEEE International Symposium on Circuits and Systems, 2005, 2223-2226 p.Conference paper, Published paper (Refereed)
Abstract [en]

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.
Series
IEEE International Symposium on Circuits and Systems, ISSN 0271-4302
Keyword [en]
Boolean functions, Graphic methods
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:kth:diva-43158DOI: 10.1109/ISCAS.2005.1465064ISI: 000232002402079Scopus ID: 2-s2.0-67649122205OAI: oai:DiVA.org:kth-43158DiVA: diva2:448193
Conference
IEEE International Symposium on Circuits and Systems 2005, ISCAS 2005; Kobe; 23 May 2005 through 26 May 2005
Note
QC 20111014Available from: 2011-10-14 Created: 2011-10-13 Last updated: 2011-10-14Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Krenz, René
By organisation
Microelectronics and Information Technology, IMIT
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 13 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf