ISSN:
1432-0541
Keywords:
Key words. Network flow, Maximum flow, Minimum cut, Multiterminal network, Realizable external flow, Mimicking network.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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) $\leq$ 10k-6 [k 2 2 k+2 ] .
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s004539910003
Permalink