Séminaire du 19 octobre 2009, 10h30: Louigi
Addario-Berry, McGill University.
Prim's algorithm and self-organized criticality, in the complete graph.
Let G=(V,E) be a graph with weights {w_e : e in E}, and assume all weights are distinct. If G is finite, then the well-known Prim's algorithm constructs its minimum spanning tree in the following manner. Starting from a single vertex v, add the smallest weight edge connecting v to any other vertex. More generally, at each step add the smallest weight edge joining some vertex that has already been "explored" to some unexplored vertex.
If G is infinite, however, Prim's algorithm does not necessarily construct a spanning tree (consider, for example, the case when the underlying graph is the two-dimensional lattice Z^2, all weights on horizontal edges are strictly less than 1/2 and all weights on vertical edges are strictly greater than 1/2).
The behaviour of Prim's algorithm for *random* edge weights is
an interesting and challenging object of study, even when the
underlying graph is extremely simple. This line of research
was initiated by McDiarmid, Johnson and Stone (1996), in the
case when the underlying graph is the complete graph
K_n. Recently Angel et. al. (2006) have studied Prim's
algorithm on regular trees with uniform random edge
weights. We study Prim's algorithm on K_n and on its
infinitary analogue Aldous' Poisson-weighted infinite
tree. Along the way, we uncover two new descriptions of the
Poisson IIC, the critical Poisson Galton-Watson tree
conditioned to survive forever. This is joint work with Simon
Griffiths and Ross Kang.
Virginie Collette
Last modified: Mon Mar 30 14:53:58 CEST 2009