An Exact Sublinear Algorithm for the Max-Flow, Vertex Disjoint Paths and Communication Problems on Random Graphs

Dorit S. Hochbaum
Additional contact information
Dorit S. Hochbaum: University of California, Berkeley, California

Operations Research, 1992, vol. 40, issue 5, 923-935

Abstract: 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.

Keywords: analysis of algorithms; computational complexity: sublinear flow algorithms; communications: communication problem on random graphs; networks/graphs; flow algorithms: algorithms for communication and max-flow on random graphs (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.5.923 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:40:y:1992:i:5:p:923-935

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().