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 \(n\) vertices has \(n^{n - 2}\) spanning trees. How could you sample one of them uniformly?
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.