Efficient Enumeration of d-Minimal Paths Under Capacity Constraints: A Zero-Suppressed Decision Diagram Approach

Abstract

We study the enumeration of all d-minimal paths in a multistate two-terminal network, where each arc has a specific capacity limit. Classical approaches based on generating functions or incremental enumeration tend to suffer from severe combinatorial explosion and require costly post-processing to recover feasible combinations. To address these limitations, we introduce a new construction method using Zero-Suppressed Binary Decision Diagrams (ZDDs) that integrates capacity constraints directly during the decision process. Our approach prunes infeasible branches on the fly and merges identical residual-capacity states to guarantee that each feasible combination is enumerated exactly once, without duplication. We show that the resulting structure is significantly more compact than conventional slot-based Binary Decision Diagrams (BDDs), especially when the feasible solution space is sparse. Experimental comparisons demonstrate that our capacity-aware ZDD achieves orders-of-magnitude improvements in both time and memory efficiency over BDD-based enumeration, even on networks with moderate size and demand values. Beyond performance, our framework provides a canonical and reusable representation of all feasible d-minimal-path combinations, which can be leveraged in reliability analysis, path planning, or network design. These findings support the relevance of ZDD-based models for exact enumeration tasks under resource constraints in real-world infrastructures.