DocumentCode
3406693
Title
A symbolic algorithm for maximum flow in 0-1 networks
Author
Hachtel, G.D. ; Somenzi, F.
Author_Institution
Dept. of Electr. & Comput. Eng., Colorado Univ., Boulder, CO, USA
fYear
1993
fDate
7-11 Nov. 1993
Firstpage
403
Lastpage
406
Abstract
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.
Keywords
symbol manipulation; 0-1 networks; edge matching problem; edge-disjoint augmenting paths; explicit enumeration; maximum flow; priority functions; symbolic algorithm; Automata; Boolean functions; Circuit testing; Data structures; Encoding; Intelligent networks; Joining processes; Sequential analysis; Sequential circuits; Very large scale integration;
fLanguage
English
Publisher
ieee
Conference_Titel
Computer-Aided Design, 1993. ICCAD-93. Digest of Technical Papers., 1993 IEEE/ACM International Conference on
Conference_Location
Santa Clara, CA, USA
Print_ISBN
0-8186-4490-7
Type
conf
DOI
10.1109/ICCAD.1993.580088
Filename
580088
Link To Document