b'@techreport{ArikatiChaudhuriZaroliagis96,'b'\nTITLE = {All-pairs min-cut in sparse networks},\nAUTHOR = {Arikati, Srinivasa and Chaudhuri, Shiva and Zaroliagis, Christos},\nLANGUAGE = {eng},\nURL = {http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1996-1-007},\nNUMBER = {MPI-I-1996-1-007},\nINSTITUTION = {Max-Planck-Institut f{\\"u}r Informatik},\nADDRESS = {Saarbr{\\"u}cken},\nYEAR = {1996},\nDATE = {1996},\nABSTRACT = {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 input $n$-vertex network so that, afterwards, 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 such networks the all-pairs min-cut 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 min-cut can be found in time $O(n + \\gamma^2 \\log \\gamma)$ and all-pairs min-cut 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.},\nTYPE = {Research Report / Max-Planck-Institut f\xc3\xbcr Informatik},\n}\n'