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

Stelios N. Neophytou; Maria K. Michael

doi:10.1109/ICCD.2014.6974724

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

Stelios N. Neophytou, Maria K. Michael

Department of Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 language	English
Title of host publication	2014 32nd IEEE International Conference on Computer Design, ICCD 2014
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	489-492
Number of pages	4
ISBN (Electronic)	9781479964925
DOIs	https://doi.org/10.1109/ICCD.2014.6974724
Publication status	Published - 3 Dec 2014
Event	32nd IEEE International Conference on Computer Design, ICCD 2014 - Seoul, Korea, Republic of Duration: 19 Oct 2014 → 22 Oct 2014

Other

Other	32nd IEEE International Conference on Computer Design, ICCD 2014
Country/Territory	Korea, Republic of
City	Seoul
Period	19/10/14 → 22/10/14

Access to Document

10.1109/ICCD.2014.6974724

Cite this

@inproceedings{16b30836364d4e9390173787b2e8516b,

title = "Optimal variable ordering in ZBDD-based path representations for directed acyclic graphs",

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.",

author = "Neophytou, {Stelios N.} and Michael, {Maria K.}",

year = "2014",

month = dec,

day = "3",

doi = "10.1109/ICCD.2014.6974724",

language = "English",

pages = "489--492",

booktitle = "2014 32nd IEEE International Conference on Computer Design, ICCD 2014",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

note = "32nd IEEE International Conference on Computer Design, ICCD 2014 ; Conference date: 19-10-2014 Through 22-10-2014",

}

Neophytou, SN & Michael, MK 2014, Optimal variable ordering in ZBDD-based path representations for directed acyclic graphs. in 2014 32nd IEEE International Conference on Computer Design, ICCD 2014., 6974724, Institute of Electrical and Electronics Engineers Inc., pp. 489-492, 32nd IEEE International Conference on Computer Design, ICCD 2014, Seoul, Korea, Republic of, 19/10/14. https://doi.org/10.1109/ICCD.2014.6974724

Optimal variable ordering in ZBDD-based path representations for directed acyclic graphs. / Neophytou, Stelios N.; Michael, Maria K.
2014 32nd IEEE International Conference on Computer Design, ICCD 2014. Institute of Electrical and Electronics Engineers Inc., 2014. p. 489-492 6974724.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

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

AU - Neophytou, Stelios N.

AU - Michael, Maria K.

PY - 2014/12/3

Y1 - 2014/12/3

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84919682613&partnerID=8YFLogxK

U2 - 10.1109/ICCD.2014.6974724

DO - 10.1109/ICCD.2014.6974724

M3 - Conference contribution

AN - SCOPUS:84919682613

SP - 489

EP - 492

BT - 2014 32nd IEEE International Conference on Computer Design, ICCD 2014

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 32nd IEEE International Conference on Computer Design, ICCD 2014

Y2 - 19 October 2014 through 22 October 2014

ER -

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

Abstract

Other

Access to Document

Other files and links

Fingerprint

Cite this