ylfink@water.waterloo.edu (ylfink) (02/05/88)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
ENUMERATIVE COMBINATORICS SEMINAR
- Wednesday, February 10, 1988
Mr. Robert P.J. Day, a graduate student of this
department, will speak on ``Unranking and Ranking
Spanning Trees of a Graph''.
TIME: 1:30 PM
ROOM: MC 5158A
ABSTRACT
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
3
develop O(n ) unranking and ranking functions for the
spanning trees of an arbitrary graph. The unranking
function maps any integer in the interval |1,s| to the
corresponding tree, while the ranking function maps a
spanning tree to the appropriate index in the interval.
3
The unranking function provides an O(n ) method for
generating uniformly-distributed random spanning trees
of a graph, a significant improvement over the more
5 3
straightforward and obvious O(n ) and O(n m) methods.