Sampling Spanning Trees: Theory and Algorithms
Usually, a connected graph has many spanning trees. And I really mean
many:
Cayley’s formula
states that the complete graph on
In my undergraduate monograph, I studied two algorithms that solve this problem in polynomial time. Despite the fact that both procedures solve the same problem, the techniques employed are quite different. The first one is a recursive procedure based on Kirchhoff’s Theorem, and the second is a random walk based algorithm (independently created) by Aldous and Broder.
Hence, by the nature of the techniques studied, the text explores algebraic combinatorics and probability theory, developing both algorithms as consequences of some foundational concepts from those areas.