Only the source’s and sink’s neighborhood matters: convergence results for unicast and multicast connections on random graphs and hypergraphs.
Muriel Médard, Jérôme Casse · 2014
We study the maximum ow on random weighted directed graphs and hypergraphs, that generalize Erdos-Renyi graphs. We show that, for a single unicast connection chosen at random, its capacity, determined by the max-ow between source and sink, converges in probability to the capacity around the sourc