Optimal variable ordering in ZBDD-based path representations for directed acyclic graphs

Author

Neophytou, Stelios N. ; Michael, Maria K.

Author_Institution

ECE Dept., Univ. of Nicosia, Nicosia, Cyprus

fYear

2014

fDate

19-22 Oct. 2014

Firstpage

489

Lastpage

492

Abstract

This work proposes a reverse topological ordering for the variables of Zero-suppressed Binary Decision Diagrams (ZBDD) which bounds their size when used to represent the paths of a Directed Acyclic Graph (DAG). Specifically, the size of a ZBDD representing all paths of a DAG is shown to be linear to the number of the edges in the DAG.

Keywords

binary decision diagrams; directed graphs; DAG; ZBDD-based path representation; directed acyclic graph; optimal variable ordering; reverse topological ordering; zero-suppressed binary decision diagram; Circuit faults; Delays; Design automation; Educational institutions; Intelligent systems; Memory management; Reactive power;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Design (ICCD), 2014 32nd IEEE International Conference on

Conference_Location

Seoul

Type

conf

DOI

10.1109/ICCD.2014.6974724

Filename

6974724

Link To Document

https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=174696