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

Stelios N. Neophytou, Maria K. Michael

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

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.

Original languageEnglish
Title of host publication2014 32nd IEEE International Conference on Computer Design, ICCD 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages489-492
Number of pages4
ISBN (Electronic)9781479964925
DOIs
Publication statusPublished - 3 Dec 2014
Event32nd IEEE International Conference on Computer Design, ICCD 2014 - Seoul, Korea, Republic of
Duration: 19 Oct 201422 Oct 2014

Other

Other32nd IEEE International Conference on Computer Design, ICCD 2014
CountryKorea, Republic of
CitySeoul
Period19/10/1422/10/14

Fingerprint Dive into the research topics of 'Optimal variable ordering in ZBDD-based path representations for directed acyclic graphs'. Together they form a unique fingerprint.

  • Cite this

    Neophytou, S. N., & Michael, M. K. (2014). Optimal variable ordering in ZBDD-based path representations for directed acyclic graphs. In 2014 32nd IEEE International Conference on Computer Design, ICCD 2014 (pp. 489-492). [6974724] Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICCD.2014.6974724