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.
Tan, R., Kawahara, J., Garciano, A., & Sin, I. (2019). A zero-suppressed binary decision diagram approach for constrained path enumeration. Proceedings of the World Congress on Engineering 2019 , 132–136. http://www.iaeng.org/publication/WCE2019/