Abstract
A Class of Graphs where Ranking Spanning Trees and Forests takes Linear Time
by: Omer Egecioglu, Jeffrey B. Remmel and S. Gill Williamson
Abstract:
Recently Remmel and Williamson defined a class of directed graphs, called filtered digraphs, and described a natural class of bijections between oriented spanning forests of these digraphs and associated classes of functions. Filtered digraphs include many specialized graphs such as complete k-partite graphs. Their bijection allowed them to give explicit formulas for various multivariate generating functions for the oriented spanning forests which arise in this context. Specializations of their generating functions include many classical formulas for the number of spanning forests that arise from the matrix tree theorem as well as new formulas for the number of spanning forests of certain directed graphs which do not follow from the matrix tree theorem. In this paper, we prove another important property of their bijection, namely, that it allows one to develop linear time algorithms for ranking and unranking spanning trees or spanning forests of filtered digraphs. In particular, this allows one to generate random spanning trees or spanning forests of a filtered digraph $G$ in linear time in the number of vertices, $n$, of $G$ where asthe best known algorithm for generating random spanning forests of an arbitrary graph is $n^{2.376}$. Moreover, our algorithm allows one to randomly generate spanning forests of the $G$ which contain a certain class of pre-specified edges.
Keywords:
Spanning tree, spanning forest, filtered digraph, multipartite graph, ranking, unranking, bijection, random generation
Date:
January 2004
Document: 2004-02
