Simple Constructions for Multiterminal Network Flow Synthesis
Dan Gusfield · SIAM Journal on Computing · 1983
The multi-terminal network flow synthesis problem is one of the few nicely solved problems in network design, and is used widely in courses and texts on combinatorial optimization as an example of an elegantly solved problem. The solution used in these texts is due to R. E. Gomory and T. C. Hu. We present two simpler algorithms which improve the original method in speed, simplicity of the needed data structures and, most importantly, in the simplicity of the networks that are constructed. The networks constructed are planar and “uniformly optimal,” permit simple flow routing methods and simple solutions to many sensitivity and postoptimality questions, and have as few edges as any networks produced by the Gomory-Hu method. Further, one algorithm constructs networks with only one node of degree larger than three, while the other algorithm constructs networks in which no node has degree greater than four.