A fast algorithm for finding common multiple-vertex dominators in circuit graphs
2005 (English)In: ASP-DAC 2005: Proceedings Of The Asia And South Pacific Design Automation Conference, IEEE , 2005, 529-532 p.Conference paper (Refereed)
In this paper we present a fast algorithm for computing common multiple-vertex dominators in circuit graphs. Dominators are widely used in CAD applications such as satisfiability checking, equivalence checking, ATPG, technology mapping, decomposition of Boolean functions and power optimization. State of the art algorithms compute single-vertex dominators in linear time. However, the rare appearance of single-vertex dominators in circuit graphs requires the investigation of a broader type of dominators and the development of algorithms to compute them. We show that our new technique is faster and computes more common multiple-vertex dominators than existing techniques.
Place, publisher, year, edition, pages
IEEE , 2005. 529-532 p.
CAD applications, Circuit graphs, Equivalence checking, Fast algorithms, Linear time, Power Optimization, Satisfiability checking, State-of-the-art algorithms, Technology mapping
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-43276ISI: 000245021700105ScopusID: 2-s2.0-84855814263ISBN: 0-7803-8736-8ISBN: 978-078038736-2OAI: oai:DiVA.org:kth-43276DiVA: diva2:448705
10th Asia and South Pacific Design Automation Conference Location: Shanghai, China Date: Jan 18-21, 2005
QC 201110182011-10-182011-10-142012-09-26Bibliographically approved