research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:
TitleComputing Mimicking Networks
Bibtex cite IDRACTI-RU1-2000-17
Journal Algorithmica
Year published 2000
Volume 26
Number 1
Pages 31-49
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 [216], S.5/ D 6 [232]. For bounded treewidth networks we show S.k/ D O.k/ [22k ], and for outerplanar networks we show S.k/ 10k 6 [k22kC2].
Shiva, Chaudhuri
Subrahmanyam, K. V.
Wagner, F.
Zaroliagis, Christos
J14-algo-mim-net-00260031.pdf (main file)
Publication ID413