All-Pairs Min-Cut in Sparse Networks

✍ Scribed by Srinivasa R Arikati; Shiva Chaudhuri; Christos D Zaroliagis

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 355 KB
• Volume: 29
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1998.0961

✦ Synopsis

Algorithms are presented for the all-pairs min-cut problem in bounded treewidth, planar, and sparse networks. The approach used is to preprocess 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 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 Ž 2 . such networks the all-pairs min-cut problem can be solved in time O n . 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 ␥ s o n . The value Ž 2 . of a min-cut can be found in time O n q ␥ log ␥ and all-pairs min-cut can be Ž 2 4 . solved in time O n q ␥ log ␥ for sparse networks.