A Lower Bound on Computing Blocking Flows in Graphs

Ketan Mulmuley; Pradyut Shah. 1 November, 2000.
Communicated by Ketan Mulmuley.


We show that the Maximum Blocking Flow problem on a graph of n vertices cannot be computed in time o(n^{1/4}) using polynomially many processors on an unbounded fan-in PRAM without bit operations, even when the bitlengths of the inputs are restricted to be of size O(n^2).

Original Document

The original document is available in Postscript (uploaded 8 June, 2001 by Dustin Mitchell).

Additional Document Formats

The document is also available in PDF (uploaded 8 June, 2001 by Dustin Mitchell).

NOTE: The author warrants that these additional documents are identical with the originial to the extent permitted by the translation between the various formats. However, the webmaster has made no effort to verify this claim. If the authenticity of the document is an issue, please always refer to the "Original document." If you find significant alterations, please report to