An Efficient Algorithm for Computing Common Double-Vertex Dominators
2006 (English)In: Proceedings of International Symposium on Applied Computing (IADIS’2006), 2006, 34-42 p.Conference paper (Refereed)
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.
Logic circuit, double-vertex dominator, dominator chain, re-converging path
Electrical Engineering, Electronic Engineering, Information Engineering
IdentifiersURN: urn:nbn:se:kth:diva-62765ISBN: 972-8924-09-7OAI: oai:DiVA.org:kth-62765DiVA: diva2:484522
IADIS International Conference. San Sebastian, Spain. 25-28 February 2006
QC 201201272012-01-272012-01-202016-05-09Bibliographically approved