Exact expectations for random graphs and assignments

Simple item page
dc.creatorEriksson, Henrik
dc.creatorEriksson, Kimmo
dc.creatorSjostrand, Jonas
dc.date2004-11-09
dc.date.accessioned2026-07-07T05:14:08Z
dc.date.available2026-07-07T05:14:08Z
dc.descriptionFor 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.
dc.description9 pages
dc.identifierhttps://arxiv.org/abs/math/0411199
dc.identifierhttp://arxiv.org/abs/math/0411199
dc.identifierCombinatorics, Probability and Computing 12, 2003, pages 401-412
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/73161
dc.subjectCombinatorics
dc.subject05C80; 05C40, 60K99
dc.titleExact expectations for random graphs and assignments
dc.typetext

Files

Collections

arXiv