Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | 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:

21 November 2019

Event End Date:

21 November 2019

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