2004/11/09 by Henrik Eriksson, Kimmo Eriksson, Jonas Sjostrand
Mathematics · #math.CO #msc:05C80 #msc:05C40 #msc:60K99
published as Combinatorics, Probability and Computing 12, 2003, pages 401-412 · 9 pages
arxiv created 2004/11/09 · arxiv updated 2009/12/01
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 the expected length of the corresponding minimal spanning forest. For a random bipartite graph we give a formula for the expected time at which a k-assignment appears. This result has bearing upon the random assignment problem.