Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     Display Documents



ID: 517992.0, MPI für Informatik / Algorithms and Complexity Group
Computing Mimicking Networks
Authors:Chaudhuri, Shiva; Subrahmanyam, K. V.; Wagner, Frank; Zaroliagis, Christos
Language:English
Publisher:Springer
Place of Publication:Berlin, Germany
Date of Publication (YYYY-MM-DD):1998
Title of Proceedings:Proceedings of the 25th International Colloquium on Automata, Languages and Programming (ICALP-98)
Start Page:556
End Page:567
Title of Series:Lecture Notes in Computer Science
Place of Conference/Meeting:Aalborg, Denmark
(Start) Date of Conference/Meeting
 (YYYY-MM-DD):
1998
Audience:Experts Only
Intended Educational Use:No
Abstract / Description:A {\em 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^22^{k+2}]$.
Last Change of the Resource (YYYY-MM-DD):2010-03-02
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Identifiers:LOCALID:C1256428004B93B8-1774120C925E283DC1256723006321B1-...
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.