Exact expectations for random graphs and assignments
2003 (English)In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 12, no 4, 401-412 p.Article in journal (Refereed) Published
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 a bearing on the random assignment problem.
Place, publisher, year, edition, pages
2003. Vol. 12, no 4, 401-412 p.
IdentifiersURN: urn:nbn:se:kth:diva-22719DOI: 10.1017/s096354830200545xISI: 000184560800003OAI: oai:DiVA.org:kth-22719DiVA: diva2:341417
QC 201005252010-08-102010-08-10Bibliographically approved