Computing mimicking networks
A mimicking network for a k-terminal network, N, is one whose realizable external flows are the same as those of N. Let S(k) denote the minimum size of a mimicking network for a k-terminal network. In this paper we give new constructions of mimicking networks and prove the following results (the values in brackets are the previously best known results): S(4) = 5 [2(16)], S(5) = 6 [2(32)]. For bounded treewidth networks we show S(k) - O(k) [2(2k)], and for outerplanar networks we show S(k) p less than or equal to 10k - 6 [k(2)2(k+2)].
mimicking network realizable external flow network flow maximum flow minimum cut multiterminal network