|Type of publication:||Article|
|Title||Computing Mimicking Networks|
|Bibtex cite ID||RACTI-RU1-2000-17|
|Year published ||2000|
|Keywords ||Network flow,Maximum flow,Minimum cut,Multiterminal network,Realizable external flow,|
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/ D 5 , S.5/ D 6 . For bounded treewidth
networks we show S.k/ D O.k/ [22k ], and for outerplanar networks we show S.k/ · 10k ¡ 6 [k22kC2].
J14-algo-mim-net-00260031.pdf (main file) |