K.V. Subrahmanyam
Max-Planck-Institut für Informatik
Im Stadtwald, D-66123 Saarbrücken
email: kv@mpi-sb.mpg.de
Frank Wagner
Freie Universität Berlin
Institut für Informatik
Takustr. 9, D-14195 Berlin
email: wagner@inf.fu-berlin.de
Chistos D. Zaroliagis
Max-Planck-Institut für Informatik
Im Stadtwald, D-66123 Saarbrücken
email: zaro@mpi-sb.mpg.de
Report B 98-01
February 1998
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. We 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^{2^{k}}]$, and for outerplanar networks we show $S(k) \leq 10k-6~[k^22^{k+2}]$.
Get the report here or by anonymous ftp: Server: fubinf.inf.fu-berlin.de File: pub/reports/tr-b-98-01.ps.gz