ALL-PAIRS MIN-CUT IN SPARSE NETWORKS

Algorithms are presented for the all-pairs min-cut problem in bounded tree-width, planar, and sparse networks. The approach used is to prepr ocess the input n-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 an O(n log n) preprocessin g of a bounded tree-width network, it is possible to find the value of a min-cut between any two vertices in constant lime. This implies tha t for such networks the all-pairs min-cut problem can be solved in tim e O(n(2)). This algorithm is used in conjunction with a graph decompos ition technique of Frederickson to obtain algorithms for sparse and pl anar networks. The running times depend upon a topological property, g amma, of the input network. The parameter gamma varies between 1 and T heta(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 m in-cut can be solved in time O(n(2) + gamma(3) log gamma) for sparse n etworks. 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 that are also outerplanar. (C) 1998 Academic Press.