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

ID: 517993.0, MPI für Informatik / Algorithms and Complexity Group
All-Pairs Min-Cut in Sparse Networks
Authors:
Language:English
Date of Publication (YYYY-MM-DD):1998
Title of Journal:Journal of Algorithms
Volume:29
Start Page:82
End Page:110
Review Status:Peer-review
Audience:Experts Only
Intended Educational Use:No
Abstract / Description:Algorithms are presented for the all-pairs min-cut problem in bounded
tree-width, planar and sparse networks. The approach used
is to preprocess the input $n$-vertex network so that, afterwards, the
value of a min-cut between any two vertices can be efficiently
computed. A tradeoff is shown between the preprocessing time and the time
taken to compute min-cuts subsequently. In particular, after
an $O(n\log n)$ preprocessing of a bounded tree-width network,
it is possible to find the value of a
min-cut between any two vertices in constant time. This implies that
for such networks the all-pairs min-cut problem can be solved
in time $O(n^2)$.
This algorithm is used in conjunction with a graph
decomposition technique of Frederickson to obtain algorithms for
sparse and planar networks. The running times depend upon a
topological property, $\gamma$, of the input network.
The parameter $\gamma$ varies between
1 and $\Theta(n)$; the algorithms perform well when $\gamma = o(n)$.
The value of a min-cut can be found in time $O(n + \gamma^2 \log \gamma)$ and all-pairs min-cut can be solved in time $O(n^2 + \gamma^4 \log \gamma)$ for sparse networks. The corresponding running times
for planar networks are $O(n+\gamma \log \gamma)$ and $O(n^2 + \gamma^3 \log \gamma)$, respectively. The latter bounds depend on a result
of independent interest: outerplanar networks have small
mimicking'' networks which are also outerplanar.
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-4F5288722A23EA07C125672300615D50-...
ISSN:0196-6774
 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.