非表示:
キーワード:
-
要旨:
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 [216] , S(5)=6 [232]
. For bounded treewidth networks we show S(k)= O(k) [2^ 2k ] , and for
outerplanar networks we show S(k) $\leq$ 10k-6 [k22k+2] .
