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

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.