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 数据挖掘交友

资料全文下载