CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Random matching problems on the complete graph

Johan Wästlund (Institutionen för matematiska vetenskaper)
Electronic Communications in Probability (1083-589X). Vol. 13 (2008), p. 258-265.
[Artikel, refereegranskad vetenskaplig]

The edges of the complete graph on n vertices are assigned independent exponentially dis- tributed costs. A k-matching is a set of k edges of which no two have a vertex in common. We obtain explicit bounds on the expected value of the minimum total cost Ck,n of a k-matching. In particular we prove that if n = 2k then π2 /12 < ECk,n < π2 /12 + log n/n.

Nyckelord: Minimum matching, exponential, expectation, mean field, network.

Denna post skapades 2009-01-15. Senast ändrad 2011-03-31.
CPL Pubid: 87351


Läs direkt!

Lokal fulltext (fritt tillgänglig)

Institutioner (Chalmers)

Institutionen för matematiska vetenskaperInstitutionen för matematiska vetenskaper (GU)


Annan matematik

Chalmers infrastruktur