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:








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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for 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