MPII961007
Allpairs mincut in sparse networks
Arikati, Srinivasa R. and Chaudhuri, Shiva and Zaroliagis, Christos D.
March 1996, 27 pages.
.
Status: available  back from printing
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 times4 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.

 Attachement: MPII961007.ps (318 KBytes); MPII961007.pdf (317 KBytes)
URL to this document: https://domino.mpiinf.mpg.de/internet/reports.nsf/NumberView/19961007
BibTeX
@TECHREPORT{ArikatiChaudhuriZaroliagis96,
AUTHOR = {Arikati, Srinivasa R. and Chaudhuri, Shiva and Zaroliagis, Christos D.},
TITLE = {Allpairs mincut in sparse networks},
TYPE = {Research Report},
INSTITUTION = {MaxPlanckInstitut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPII961007},
MONTH = {March},
YEAR = {1996},
ISSN = {0946011X},
}