


ID:
517993.0,
MPI für Informatik / Algorithms and Complexity Group 
AllPairs MinCut in Sparse Networks 
Authors:  Arikati, Srinivasa Rao; Chaudhuri, Shiva; Zaroliagis, Christos  Language:  English  Date of Publication (YYYYMMDD):  1998  Title of Journal:  Journal of Algorithms  Volume:  29  Start Page:  82  End Page:  110  Review Status:  Peerreview  Audience:  Experts Only  Intended Educational Use:  No  Abstract / Description:  Algorithms are presented for the allpairs mincut problem in bounded treewidth, planar and sparse networks. The approach used is to preprocess the input $n$vertex network so that, afterwards, the value of a mincut between any two vertices can be efficiently computed. A tradeoff is shown between the preprocessing time and the time taken to compute mincuts subsequently. In particular, after an $O(n\log n)$ preprocessing of a bounded treewidth network, it is possible to find the value of a mincut between any two vertices in constant time. This implies that for such networks the allpairs mincut 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 mincut can be found in time $O(n + \gamma^2 \log \gamma)$ and allpairs mincut 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 (YYYYMMDD):  20100302  External Publication Status:  published  Document Type:  Article 
Communicated by:  Kurt Mehlhorn  Affiliations:  MPI für Informatik/Algorithms and Complexity Group
 Identifiers:  LOCALID:C1256428004B93B84F5288722A23EA07C125672300615D50... ISSN:01966774  


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.

