Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-08T13:27:34.409Z Has data issue: false hasContentIssue false
  • English
  • Français

Exact Expectations for Random Graphs and Assignments

Published online by Cambridge University Press:  04 July 2003

HENRIK ERIKSSON ,
KIMMO ERIKSSON  and
JONAS SJÖSTRAND
HENRIK ERIKSSON
Affiliation:
NADA, KTH, SE-100 44 Stockholm, Sweden (e-mail: henrik@nada.kth.se
KIMMO ERIKSSON
Affiliation:
IMA, Mälardalens högskola, Box 883, SE-721 23 Västerås, Sweden (e-mail: kimmo.eriksson@mdh.se)
JONAS SJÖSTRAND
Affiliation:
NADA, KTH, SE-100 44 Stockholm, Sweden (e-mail: jonass@nada.kth.se)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 12 , Issue 4 , July 2003 , pp. 401 - 412
Copyright
2003 Cambridge University Press