research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:
TitleAll-Pairs Min-Cut in Sparse Networks
Bibtex cite IDRACTI-RU1-1998-4
Journal Journal of Algorithms
Year published 1998
Volume 29
Number 1
Pages 82-110
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 inputn-vertex network so that afterward, 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 anO(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 timeO(n2). 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, ã, of the input network. The parameter ã varies between 1 and È(n); the algorithms perform well when ã = o(n). The value of a min-cut can be found in timeO(n + ã2log ã) and all-pairs min-cut can be solved in timeO(n2 + ã4log ã) for sparse networks. The corresponding running times for planar networks areO(n + ã log ã) andO(n2 + ã3log ã), respectively. The latter bounds depend on a result of independent interest; outerplanar networks have small “mimicking” networks that are also outerplanar.
Srinivasa, Arikati
Shiva, Chaudhuri
Zaroliagis, Christos
all-pairs.pdf (main file)
Publication ID856