A symbolic algorithm for maximum flow in 0-1 networks
Gary D. Hachtel, Fabio Somenzi · International Conference on Computer Aided Design · 1993
We present an algorithm for finding the maximum flow in a 0-1 network. The algorithm is symbolic and avoids explicit enumeration of the nodes and edges of the network. Therefore, it can handle much larger graphs than it was previously possible (more than 10/sup 36/ edges). The main idea is to trace (implicitly) sets of edge-disjoint augmenting paths. Disjointness is enforced by solving an edge matching problem for each layer of the network with the help of newly defined priority functions.