Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor(s)
 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: (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},
}