Journal Article
@Article
Artikel in Fachzeitschrift
Show entries of:
this year
(2023) |
last year
(2022) |
two years ago
(2021) |
Notes URL
Action:
login to update
Options:
Goto entry point
Author, Editor(s)
Author(s):
Arikati, Srinivasa Rao
Chaudhuri, Shiva
Zaroliagis, Christos
dblp
dblp
dblp
BibTeX cite key*:
Arikati-Chaudhuri-Zaroliagis-98
Title
Title*:
All-Pairs Min-Cut in Sparse Networks
Journal
Journal Title*:
Journal of Algorithms
Journal's URL:
Download URL
for the article:
Language:
English
Publisher
Publisher's
Name:
Publisher's URL:
Publisher's
Address:
ISSN:
0196-6774
Vol, No, pp, Date
Volume*:
29
Number:
Publishing Date:
1998
Pages*:
82-110
Number of
VG Pages:
Page Start:
Page End:
Sequence Number:
DOI:
Note, Abstract, ©
Note:
(LaTeX) Abstract:
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.
URL for the Abstract:
Categories,
Keywords:
HyperLinks / References / URLs:
Copyright Message:
Personal Comments:
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:
@ARTICLE
{
Arikati-Chaudhuri-Zaroliagis-98
,
AUTHOR = {Arikati, Srinivasa Rao and Chaudhuri, Shiva and Zaroliagis, Christos},
TITLE = {All-Pairs Min-Cut in Sparse Networks},
JOURNAL = {Journal of Algorithms},
YEAR = {1998},
VOLUME = {29},
PAGES = {82--110},
ISBN = {0196-6774},
}
Entry last modified by Uwe Brahm, 03/02/2010
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 18:43:28
Revisions
3.
2.
1.
0.
Editor(s)
Uwe Brahm
Uwe Brahm
Christos Zaroliagis
Christos Zaroliagis
Edit Dates
04.04.2000 11:11:03
30.03.99 22:40:50
25/02/99 19:13:42
25/02/99 18:43:28