Physical Sciences and Mathematics Commons^™

A Zero-Suppressed Binary Decision Diagram Approach For Constrained Path Enumeration, Renzo Roel P. Tan, Jun Kawahara, Agnes Garciano, Immanuel Sin

Mathematics Faculty Publications

Combinatorial optimization over graphs has been the subject of research. Recently, the solution of such problems by enumeration using a compact data structure called the zero-suppressed binary decision diagram was proposed and studied. The paper augments the existing frontier-based search method of construction and puts forth a technique for accommodating additional constraints during computation. The shortest and longest path problems for the Osaka Metro transit network are simultaneously solved as demonstration. Furthermore, a comparison of the approach with a conventional integer programming method is presented towards justifying the effectiveness of the algorithm.