A class of graphs which has efficient ranking and upranking algorithms for spanning trees and forests
Remmel and Williamson recently 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 [12]. Filtered digraphs include many specialized graphs such as complete k-partite graphs. The Remmel-Williamson bijections provide explicit formulas for various multivariate generating functions for the oriented spanning forests which arise in this context. In this paper, we prove another important property of these bijections, namely, that it allows one to construct efficient algorithms for ranking and unranking spanning trees or spanning forests of filtered digraphs G. For example, we show that if G = (V, E) is a filtered digraph and SP(G) is the collection of spanning trees of G, then our algorithm requires O(\V\) operations of sum, difference, product, quotient, and comparison of numbers less than or equal \SP(G)\ to rank or unrank spanning trees of G.
graph ranking spanning tree filtered digraph spanning forest unranking complete bipartite graph combinatorial generation enumeration