MPI-INF D1 Publications: Journal Article: Computing mimicking networks

Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | Notes URL

Action:

Options:

Goto entry point

Author, Editor(s)

Author(s):

Chaudhuri, Shiva
Subrahmanyam, K. V.
Wagner, Frank
Zaroliagis, Christos

dblp
dblp
dblp
dblp

BibTeX cite key*:

ChaudhuriSubrahmanyamWagnerZaroliagis2000

Title

Title*:

Computing mimicking networks

Journal

Journal Title*:	Algorithmica	Journal's URL:	http://link.springer-ny.com/link/service/journals/00453/
Download URL for the article:		Language:	English

Publisher

Publisher's Name:	Springer	Publisher's URL:
Publisher's Address:	New York, USA	ISSN:	0178-4617

Vol, No, pp, Date

Volume*:	26	Number:	1
Publishing Date:	2000
Pages*:	31-49	Number of VG Pages:
Page Start:		Page End:
Sequence Number:		DOI:

Note, Abstract, ©

Note:
(LaTeX) 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)=5 [216] , S(5)=6 [232] . For bounded treewidth networks we show S(k)= O(k) [2^ 2k ] , and for outerplanar networks we show S(k) $\leq$ 10k-6 [k22k+2] .
URL for the Abstract:
Categories, Keywords:
HyperLinks / References / URLs:
Copyright Message:
Personal Comments:
Download Access Level:	Public

Correlation

MPG Unit:	Max-Planck-Institut für Informatik

MPG Subunit:	Algorithms and Complexity Group
Audience:	Expert
Appearance:	MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{ChaudhuriSubrahmanyamWagnerZaroliagis2000,
AUTHOR = {Chaudhuri, Shiva and Subrahmanyam, K. V. and Wagner, Frank and Zaroliagis, Christos},
TITLE = {Computing mimicking networks},
JOURNAL = {Algorithmica},
PUBLISHER = {Springer},
YEAR = {2000},
NUMBER = {1},
VOLUME = {26},
PAGES = {31--49},
ADDRESS = {New York, USA},
ISBN = {0178-4617},
}

Entry last modified by Christine Kiesel, 03/02/2010

Edit History (please click the blue arrow to see the details)

	Editor(s) Anja Becker	Created 03/14/2001 15:02:04
Revisions 4. 3. 2. 1. 0.	Editor(s) Christine Kiesel Christine Kiesel Uwe Brahm Anja Becker Anja Becker	Edit Dates 30.05.2005 15:34:49 09.06.2004 16:43:57 05/02/2001 11:26:58 AM 15.03.2001 10:35:41 14.03.2001 15:09:24

Attachment Section