Exact expectations for random graphs and assignments

Henrik Eriksson, Kimmo Eriksson, Jonas Sjostrand

For a random graph on n vertices where the edges appear with individual rates, we give exact formulas for the expected time at which the number of components has gone down to k and…