|
This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies.
For more information visit Aigaion.nl. | |
Type of publication: | Article |
Entered by: | |
Title | Computing Mimicking Networks |
Bibtex cite ID | RACTI-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, |
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/ 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]. |
Authors | |
Topics
| |
BibTeX | BibTeX |
RIS | RIS |
Attachments |
J14-algo-mim-net-00260031.pdf (main file) |
|
Publication ID | 413 |
|
|