elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

Approximate BDD Minimization by Weighted A*

Ebendt, Rüdiger and Drechsler, Rolf (2009) Approximate BDD Minimization by Weighted A*. In: IEEE International Symposium on Circuits and Systems, pp. 2974-2977. ISCAS 2009, 2009-05-24 - 2009-05-27, Taipei (Taiwan R.o.C.). ISBN 978 1 4244 3827 3

[img]
Preview
PDF
143kB

Abstract

Reduced ordered Binary Decision Diagrams (BDDs) are a data structure for efficient representation and manipulation of Boolean functions. They are frequently used in logic synthesis. The size of BDDs depends on a chosen variable ordering, i.e. the size may vary from linear to exponential, and the existence of a polynomial algorithm to approximate the optimal variable ordering of BDDs implies P = NP. In this paper, a new approximate BDD minimization algorithm is presented which is based on weighted A*. When compared to the best known previous method, large gains in run time are observed whereas the degradation of solution quality is considerably smaller than for the previous method. The improved behavior now allows for a wider range of time/quality tradeoffs. Experimental results demonstrate the efficiency of the new approach.

Item URL in elib:https://elib.dlr.de/63457/
Document Type:Conference or Workshop Item (Poster)
Title:Approximate BDD Minimization by Weighted A*
Authors:
AuthorsInstitution or Email of AuthorsAuthors ORCID iD
Ebendt, RüdigerUNSPECIFIEDUNSPECIFIED
Drechsler, RolfUniversität BremenUNSPECIFIED
Date:2009
Journal or Publication Title:IEEE International Symposium on Circuits and Systems
Refereed publication:Yes
Open Access:Yes
Gold Open Access:No
In SCOPUS:No
In ISI Web of Science:No
Page Range:pp. 2974-2977
Editors:
EditorsEmail
IEEE Circuits and Systems (CAS) Society, IEEE CASUNSPECIFIED
Series Name:IEEE Conference Proceedings (IEEE CNF)
ISBN:978 1 4244 3827 3
Status:Published
Keywords:routing, shortest path, Dijkstra, A*
Event Title:ISCAS 2009
Event Location:Taipei (Taiwan R.o.C.)
Event Type:Conference
Event Dates:2009-05-24 - 2009-05-27
Organizer:IEEE, IEEE CAS Society
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Transport
HGF - Program Themes:Transport System
DLR - Research area:Transport
DLR - Program:V VS - Verkehrssystem
DLR - Research theme (Project):V - Mittel- und langfristige Entwicklung der Personenverkehrsnachfrage (old)
Location: Berlin-Adlershof
Institutes and Institutions:Institute of Transportation Systems > Traffic Management
Deposited By: Ebendt, Dr.rer.nat. Rüdiger
Deposited On:05 Mar 2010 09:55
Last Modified:31 Jul 2019 19:27

Repository Staff Only: item control page

Browse
Search
Help & Contact
Information
electronic library is running on EPrints 3.3.12
Copyright © 2008-2017 German Aerospace Center (DLR). All rights reserved.