Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2020) | last year (2019) | two years ago (2018) | Notes URL

Action:

login to update
Options:








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

URL of the conference:


URL for downloading the paper:


Event Address*:

Aalborg, Denmark
Language:

English

Event Date*
(no longer used):

July, 11-15
Organization:


Event Start Date:

20 January 2020
Event End Date:

20 January 2020

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 07:02:46 PM
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