Path: utzoo!utgpu!water!ylfink
From: ylfink@water.waterloo.edu (ylfink)
Newsgroups: ont.events,uw.talks
Subject: Unranking and Ranking Spanning Trees of a Graph.
Keywords: Mr. Robert P.J. Day, Wed., Feb. 10/88, 1:30 PM, MC 5158A.
Message-ID: <1400@water.waterloo.edu>
Date: 4 Feb 88 19:25:45 GMT
Distribution: ont
Organization: U of Waterloo, Ontario
Lines: 35



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.