Computing mimicking networks

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

Local TagsRelease HistoryDetailsSummary

Computing mimicking networks

Chaudhuri, S., Subrahmanyam, K. V., Wagner, F., & Zaroliagis, C. (2000). Computing mimicking networks. Algorithmica, 26(1), 31-49.

Item is Released

show all hide all

Basic

show hide

Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3393-0 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3394-E

Genre: Journal Article

Files

show Files

Locators

show

Creators

show

hide

Creators:
Chaudhuri, Shiva¹, Author
Subrahmanyam, K. V.¹, Author
Wagner, Frank¹, Author
Zaroliagis, Christos¹, Author

Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019

Content

show

hide

Free keywords: -

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] .

Details

show

hide

Language(s): eng - English

Dates: Modified: 2010-03-02Date issued: 2000

Publication Status: Issued

Pages: -

Publishing info: -

Table of Contents: -

Rev. Type: Peer

Identifiers: eDoc: 518151
Other: Local-ID: C1256428004B93B8-5EE8B1BB2C1A5F68C1256A0F004D1844-ChaudhuriSubrahmanyamWagnerZaroliagis2000

Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show

hide

Title: Algorithmica

Source Genre: Journal

Creator(s):

Affiliations:

Publ. Info: -

Pages: - Volume / Issue: 26 (1) Sequence Number: - Start / End Page: 31 - 49 Identifier: ISSN: 0178-4617