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

ID: 518151.0, MPI für Informatik / Algorithms and Complexity Group
Computing mimicking networks
Authors:
Language:English
Date of Publication (YYYY-MM-DD):2000
Title of Journal:Algorithmica
Volume:26
Issue / Number:1
Start Page:31
End Page:49
Review Status:Peer-review
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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] .
Last Change of the Resource (YYYY-MM-DD):2010-03-02
External Publication Status:published
Document Type:Article
Communicated by:Kurt Mehlhorn
Affiliations:
Identifiers:LOCALID:C1256428004B93B8-5EE8B1BB2C1A5F68C1256A0F004D1844-...
ISSN:0178-4617
 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.