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 Computing Common Double-Vertex Dominators
KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.ORCID iD: 0000-0001-7382-9408
KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
2006 (English)In: Proceedings of International Symposium on Applied Computing (IADIS’2006), 2006, 34-42 p.Conference paper, Published paper (Refereed)
Abstract [en]

Graph dominators provide a general mechanism for identifying re-converging paths in logic circuits. This is useful in anumber of problems in Computer-Aided Design including computation of signal probabilities for test generation,switching activities for power and noise analysis, cut point selection in equivalence checking, etc. Single-vertexdominators are too rare in circuit graphs to handle re-converging paths in a practical way. This paper focuses on doublevertexdominators, which occur more frequently. We present an algorithm for computing common double-vertexdominators for a set of m vertices. Previous approaches required O(n2) time, while the presented one is O(m log(n)),where n is the number of vertices in the circuit graph. The experimental results show that, on average, the presentedalgorithm is twice faster than the previous techniques.

Place, publisher, year, edition, pages
2006. 34-42 p.
Keyword [en]
Logic circuit, double-vertex dominator, dominator chain, re-converging path
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:kth:diva-62765ISBN: 972-8924-09-7 (print)OAI: oai:DiVA.org:kth-62765DiVA: diva2:484522
Conference
IADIS International Conference. San Sebastian, Spain. 25-28 February 2006
Note

QC 20120127

Available from: 2012-01-27 Created: 2012-01-20 Last updated: 2016-05-09Bibliographically approved

Open Access in DiVA

No full text

Other links

http://www.iadisportal.org/digital-library/an-efficient-algorithm-for-computing-common-double-vertex-dominators

Authority records BETA

Dubrova, Elena

Search in DiVA

By author/editor
Teslenko, MaximDubrova, ElenaTenhunen, Hannu
By organisation
Electronic, Computer and Software Systems, ECS
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

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