AN EXACT SUBLINEAR ALGORITHM FOR THE MAX-FLOW, VERTEX DISJOINT PATHS AND COMMUNICATION PROBLEMS ON RANDOM GRAPHS
成果类型：
Article
署名作者：
HOCHBAUM, DS
署名单位：
University of California System; University of California Berkeley
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.40.5.923
发表日期：
1992
页码：
923-935
关键词：
摘要：
This paper describes a randomized algorithm for solving the maximum-flow maximum-cut problem on connected random graphs. The algorithm is very fast-it does not look up most vertices in the graph. Another feature of this algorithm is that it almost surely provides, along with an optimal solution, a proof of optimality of the solution. In addition, the algorithm's solution is, by construction, a collection of vertex-disjoint paths which is maximum. Under a restriction on the graph's density, an optimal solution to the NP-hard communication problem is provided as well, that is, finding a maximum collection of vertex-disjoint paths between sender-receiver pairs of terminals. The algorithm lends itself to a sublogarithmic parallel and distributed implementation. Its effectiveness is demonstrated via extensive empirical study.