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

DOI10.1287/opre.40.5.923zbMath0769.90033OpenAlexW1968084791MaRDI QIDQ4015475

Dorit S. Hochbaum

Publication date: 5 January 1993

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.40.5.923

zbMATH Keywords

randomized algorithmconnected random graphsmaximum-flow maximum-cutNP-hard communication problemsublogarithmic parallel and distributed implementation

Mathematics Subject Classification ID

Communication networks in operations research (90B18) Stochastic network models in operations research (90B15) Parallel numerical computation (65Y05) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (2)

Rolling backwards can move you forward: On embedding problems in sparse expanders ⋮ Optimal Construction of Edge-Disjoint Paths in Random Graphs

This page was built for publication: An Exact Sublinear Algorithm for the Max-Flow, Vertex Disjoint Paths and Communication Problems on Random Graphs