On Mimicking Networks

Shiva Chaudhuri
Max-Planck-Institut für Informatik
Im Stadtwald, D-66123 Saarbrücken
email: shiva@mpi-sb.mpg.de

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