The set S of spanning trees of an n-vertex graph G can be placed in one-to-one correspondence with the integers in the interval [1, s], where s = |S|. We develop O(n3) unranking and ranking functions for the spanning trees of an arbitrary graph. The unranking function maps any interval [1, s] to the corresponding tree, while the ranking function maps a spanning tree to the appropriate index in the interval. The unranking function provides an O(n3) method for generating a random spanning tree of a graph with uniform distribution.
ASJC Scopus subject areas
- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics