Approximate BDD Minimization by Weighted A*

Ebendt, Rüdiger und Drechsler, Rolf (2008) Approximate BDD Minimization by Weighted A*. In: IEEE International Symposium on Circuits and Systems. ISCAS 2009, 2009-05-24 - 2009-05-27, Taipei (Taiwan R.o.C.). (im Druck)

Es ist eine neuere Version dieses Eintrags verfügbar.

Vorschau

PDF
143kB

Kurzfassung

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.

elib-URL des Eintrags:

https://elib.dlr.de/58055/

Dokumentart:

Konferenzbeitrag (Poster)

Titel:

Approximate BDD Minimization by Weighted A*

Autoren:

Autoren	Institution oder E-Mail-Adresse	Autoren-ORCID-iD	ORCID Put Code
Ebendt, Rüdiger	NICHT SPEZIFIZIERT	NICHT SPEZIFIZIERT	NICHT SPEZIFIZIERT
Drechsler, Rolf	Universität Bremen	NICHT SPEZIFIZIERT	NICHT SPEZIFIZIERT

Datum:

2008

Erschienen in:

IEEE International Symposium on Circuits and Systems

Referierte Publikation:

Open Access:

Gold Open Access:

Nein

In SCOPUS:

Nein

In ISI Web of Science:

Nein

Herausgeber:

Herausgeber	Institution und/oder E-Mail-Adresse der Herausgeber	Herausgeber-ORCID-iD	ORCID Put Code
IEEE Circuits and Systems (CAS) Society,	NICHT SPEZIFIZIERT	NICHT SPEZIFIZIERT	NICHT SPEZIFIZIERT

Name der Reihe:

IEEE Conference Proceedings (IEEE CNF)

Status:

im Druck

Stichwörter:

routing, shortest path, Dijkstra, A*

Veranstaltungstitel:

ISCAS 2009

Veranstaltungsort:

Taipei (Taiwan R.o.C.)

Veranstaltungsart:

internationale Konferenz

Veranstalter :

IEEE, IEEE CAS Society

HGF - Forschungsbereich:

Luftfahrt, Raumfahrt und Verkehr

HGF - Programm:

Verkehr

HGF - Programmthema:

Verkehrssystem

DLR - Schwerpunkt:

Verkehr

DLR - Forschungsgebiet:

V VS - Verkehrssystem

DLR - Teilgebiet (Projekt, Vorhaben):

V - Mittel- und langfristige Entwicklung der Personenverkehrsnachfrage (alt)

Standort:

Berlin-Adlershof

Institute & Einrichtungen:

Institut für Verkehrssystemtechnik > Verkehrsmanagement

Hinterlegt von:

Ebendt, Dr.rer.nat. Rüdiger

Hinterlegt am:

20 Apr 2009

Letzte Änderung:

31 Jul 2019 19:24

Verfügbare Versionen dieses Eintrags

Approximate BDD Minimization by Weighted A*. (deposited 20 Apr 2009) [Gegenwärtig angezeigt]
- Approximate BDD Minimization by Weighted A*. (deposited 17 Aug 2009 14:30)
  - Approximate BDD Minimization by Weighted A*. (deposited 05 Mär 2010 09:55)

Nur für Mitarbeiter des Archivs: Kontrollseite des Eintrags