MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Chaudhuri, Shiva
Subrahmanyam, K. V.
Wagner, Frank
Zaroliagis, Christos		dblp
dblp
dblp
dblp
Editor(s):
Larsen, Kim G.
Skyum, Sven
Winskel, Glynn		dblp
dblp
dblp
BibTeX cite key*:
Chauduri-Subrahmanyam-Wagner-Zaroliagis-98
Title, Booktitle
Title*:
Computing Mimicking Networks
Booktitle*:
Proceedings of the 25th International Colloquium on Automata, Languages and Programming (ICALP-98)
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Aalborg, Denmark
Language:
English
Event Date*
(no longer used):
July, 11-15
Organization:
Event Start Date:
5 February 2023
Event End Date:
5 February 2023
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
1443
Number:
Month:
Pages:
556-567
Year*:
1998
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
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}]$.
Download
Access Level:

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{Chauduri-Subrahmanyam-Wagner-Zaroliagis-98,
AUTHOR = {Chaudhuri, Shiva and Subrahmanyam, K. V. and Wagner, Frank and Zaroliagis, Christos},
 EDITOR = {Larsen, Kim G. and Skyum, Sven and Winskel, Glynn},
 TITLE = {Computing Mimicking Networks},
 BOOKTITLE = {Proceedings of the 25th International Colloquium on Automata, Languages and Programming (ICALP-98)},
 PUBLISHER = {Springer},
 YEAR = {1998},
 VOLUME = {1443},
 PAGES = {556--567},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Aalborg, Denmark},
}

Entry last modified by Evelyn Haak, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Christos Zaroliagis		Created
02/25/1999 19:02:46
Revisions
10.
9.
8.
7.
6.		Editor(s)
Evelyn Haak
Uwe Brahm
Uwe Brahm
Uwe Brahm
Uwe Brahm		Edit Dates
01/04/99 12:24:22
01.04.99 09:41:09
01.04.99 09:38:46
29.03.99 18:52:12
29.03.99 18:47:24