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
An efficient algorithm for finding double-vertex dominators in circuit graphs
KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.ORCID iD: 0000-0001-7382-9408
2005 (English)In: DESIGN, AUTOMATION AND TEST IN EUROPE CONFERENCE AND EXHIBITION, VOLS 1 AND 2, PROCEEDINGS / [ed] Wehn, N; Benini, L, 2005, 406-411 p.Conference paper, Published paper (Refereed)
Abstract [en]

Graph dominators provide a general mechanism for identifying re-converging paths in circuits. This is useful in a number of CAD applications including computation of signal probabilities for test generation, switching activities for power and noise analysis, statistical timing analysis, cut point selection in equivalence checking, etc. Single-vertex dominators are too rare in circuit graphs to handle re-converging paths in a practical way. This paper addresses the problem of finding double-vertex dominators, which occur more frequently. First, we introduce a data structure, called dominator chain, which allows representing all possible O(n(2)) double-vertex dominators of a given vertex in O(n) space, where n is the number of vertices of the circuit graph. Dominator chains can be efficiently manipulated, e.g. it takes constant time to look-up whether a given pair of vertices is a double-vertex dominator. Second, we present an efficient algorithm for finding double-vertex dominators. The experimental results show that the presented algorithm is an order of magnitude faster than existing algorithms for finding double-vertex dominators. Thus, it is suitable for running in an incremental manner during logic synthesis.

Place, publisher, year, edition, pages
2005. 406-411 p.
Series
Design Automation and Test in Europe Conference and Expo, ISSN 1530-1591
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-42780DOI: 10.1109/DATE.2005.53ISI: 000228086900075Scopus ID: 2-s2.0-33646927539ISBN: 0-7695-2288-2 (print)OAI: oai:DiVA.org:kth-42780DiVA: diva2:447742
Conference
Design, Automation and Test in Europe Conference and Exhibition (DATE 05) Location: Munich, GERMANY Date: MAR 07-11, 2005
Note

QC 20111013

Available from: 2011-10-13 Created: 2011-10-12 Last updated: 2012-11-01Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Dubrova, Elena

Search in DiVA

By author/editor
Teslenko, MaximDubrova, Elena
By organisation
Microelectronics and Information Technology, IMIT
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 28 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