|
Title:
|
AN EFFICIENT ALGORITHM FOR COMPUTING COMMON DOUBLE-VERTEX DOMINATORS |
|
Author(s):
|
Maxim Teslenko , Elena Dubrova , Hannu Tenhunen |
|
ISBN:
|
972-8924-09-7 |
|
Editors:
|
Nuno Guimarães, Pedro Isaías and Ambrosio Goikoetxea |
|
Year:
|
2006 |
|
Edition:
|
Single |
|
Keywords:
|
Logic circuit, double-vertex dominator, dominator chain, re-converging path. |
|
Type:
|
Full Paper |
|
First Page:
|
34 |
|
Last Page:
|
41 |
|
Language:
|
English |
|
Cover:
|
|
|
Full Contents:
|
click to dowload 
|
|
Paper Abstract:
|
Graph dominators provide a general mechanism for identifying re-converging paths in logic circuits. This is useful in a number 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-vertex dominators are too rare in circuit graphs to handle re-converging paths in a practical way. This paper focuses on double-vertex dominators, which occur more frequently. We present an algorithm for computing common double-vertex dominators for a set of m vertices. Previous approaches required O(n2) time, while the presented one is O(m log(n)),wheren is the number of vertices in the circuit graph. The experimental results show that, on average, the presented algorithm is twice faster than the previous techniques. |
|
|
|
|
|
|
