Computing mimicking networks

A mimicking network for a k-terminal network, N, is one whose realizable ex ternal flows are the same as those of N. Let S(k) denote the minimum size o f a mimicking network for a k-terminal network. In this paper we give new c onstructions of mimicking networks and prove the following results (the val ues 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)].