Computing Mimicking Networks |
| |
| Authors: | S Chaudhuri K V Subrahmanyam F Wagner C D Zaroliagis |
| |
| Affiliation: | Max-Planck-Institut für Informatik, Im Stadtwald, 66123 Saarbrücken, Germany. shiva@mpi-sb.mpg.de, kv@mpi-sb.mpg.de, zaro@mpi-sb.mpg.de., DE
Institut für Informatik, Freie Universit?t Berlin, Takustrasse 9, 14195 Berlin, Germany. wagner@inf.fu-berlin.de., DE
|
| |
| Abstract: | 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 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)
10k-6 k
2
2
k+2
] .
Received April 1, 1997; revised December 10, 1997. |
| |
| Keywords: | , Network flow, Maximum flow, Minimum cut, Multiterminal network, Realizable external flow, Mimicking network, |
| 本文献已被 SpringerLink 等数据库收录！ |
|
