Kirchhoff's matrix-tree theorem states that the number of spanning trees of a graph G is equal to the value of the determinant of the reduced Laplacian of @math . We outline an efficient bijective proof of this theorem, by studying a canonical finite abelian group attached to @math whose order is equal to the value of same matrix determinant. More specifically, we show how one can efficiently compute a bijection between the group elements and the spanning trees of the graph. The main ingredient for computing the bijection is an efficient algorithm for finding the unique @math -parking function (reduced divisor) in a linear equivalence class defined by a chip-firing game. We also give applications, including a new and completely algebraic algorithm for generating random spanning trees. Other applications include algorithms related to chip-firing games and sandpile group law, as well as certain algorithmic problems about the Riemann-Roch theory on graphs.
The Uniform Spanning Tree (UST) problem has been extensively studied in the literature and there are two known types of algorithms: determinant based algorithms (e.g. @cite_2 @cite_11 @cite_22 ), and random walk based algorithms (e.g. @cite_20 @cite_12 @cite_33 ).
@cite_22 @cite_33 @cite_2 @cite_20 @cite_12 @cite_11
1968057111 2018691712 2111933629 1985234177 2062877152
Let E be a finite set and B be a given set of subsets of E. Let w(B) be a positive weight of B ∈ B. In this paper we develop an algorithm to generate a random subset U ∈ B such that the P(U = B) is proportioned to w(B). If the complexity of computing sums of the weights of B contained in set-intervals in B is O(f(∥E∥)), then the algorithm developed here has complexity O(∥E∥f(∥E∥)). The algorithm is specialized to the following cases: (i) B = all subsets of E, (ii) B = all subsets of E with k elements, (iii) B = all spanning trees in a network, and (iv) B = all paths in a directed acyclic network. Different types of weight functions are considered. It is shown that this proposed algorithm unifies many existing algorithms. Abstract Dans cet article, nous proposons un algorithme de complexite polynomiale pour construire un arbre au hasard qui soit un graphe partiel d'un graphe donne. Il consiste essentielleement a construire une arborescence de rang donne sur ce graphe, l'ensemble des arborescences etant ordonne par rapport aux valeurs croissantes de la racine et a racine egale suivant l'ordre lexicographique du codage utilise pour les arborescences. The author describes a probabilistic algorithm that, given a connected, undirected graph G with n vertices, produces a spanning tree of G chosen uniformly at random among the spanning trees of G. The expected running time is O(n log n) per generated tree for almost all graphs, and O(n sup 3 ) for the worst graphs. Previously known deterministic algorithms are much more complicated and require O(n sup 3 ) time per generated tree. A Markov chain is called rapidly mixing if it gets close to the limit distribution in time polynomial in the log of the number of states. Starting from the analysis of the above algorithm, it is shown that the Markov chain on the space of all spanning trees of a given graph where the basic step is an edge swap is rapidly mixing. > A random walk on a finite graph can be used to construct a uniform random spanning tree. It is shown how random walk techniques can be applied to the study of several properties of the uniform random spanning tree: the proportion of leaves, the distribution of degrees, and the diameter. Colbourn, Day, and Nel developed the first algorithm requiring at mostO(n3) arithmetic operations for ranking and unranking spanning trees of a graph (nis the number of vertices of the graph). We present two algorithms for the more general problem of ranking and unranking rooted spanning arborescences of a directed graph. The first is conceptually very simple and requiresO(n3) arithmetic operations. The second approach shows that the number of arithmetic operations can be reduced to the same as that of the best known algorithms for matrix multiplication.