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
2162375967 2088797223 2592535728 2038652993
The uniform spanning forest (USF) in ℤ d is the weak limit of random, uniformly chosen, spanning trees in [−n, n] d . Pemantle [11] proved that the USF consists a.s. of a single tree if and only if d ≤ 4. We prove that any two components of the USF in ℤ d are adjacent a.s. if 5 ≤ d ≤ 8, but not if d ≥ 9. More generally, let N(x, y) be the minimum number of edges outside the USF in a path joining x and y in ℤ d . Then @math Given an undirected, connected, weighted graph, the leaf-constrained minimum spanning tree (LCMST) problem seeks a spanning tree of the graph with smallest weight among all spanning trees of the graph, which contains at least l leaves. In this paper we have proposed two new metaheuristic approaches for the LCMST problem. One is an ant-colony optimization (ACO) algorithm, whereas the other is a tabu search based algorithm. Similar to a previously proposed genetic algorithm, these metaheuristic approaches also use the subset coding that represents a leaf-constrained spanning tree by the set of its interior vertices. Our new approaches perform well in comparison with two best heuristics reported in the literature for the problem — the subset-coded genetic algorithm and a greedy heuristic. Distributed minimum spanning tree (MST) problem is one of the most central and fundamental problems in distributed graph algorithms. Kutten and Peleg [KP98] devised an algorithm with running time O(D + √n . log* n), where D is the hop-diameter of the input n-vertex m-edge graph, and with message complexity O(m + n3 2). Peleg and Rubinovich [PR99] showed that the running time of the algorithm of [KP98] is essentially tight, and asked if one can achieve near-optimal running time together with near-optimal message complexity. In a recent breakthrough, [PRS16] answered this question in the affirmative, and devised a randomized algorithm with time O(D+ √n) and message complexity O(m). They asked if such a simultaneous time- and message-optimality can be achieved by a deterministic algorithm. In this paper, building upon the work of [PRS16], we answer this question in the affirmative, and devise a deterministic algorithm that computes MST in time O((D + √n). log n), using O(m . log n + n log n . log* n) messages. The polylogarithmic factors in the time and message complexities of our algorithm are significantly smaller than the respective factors in the result of [PRS16]. Also, our algorithm and its analysis are very simple and self-contained, as opposed to rather complicated previous sublinear-time algorithms [GKP98,KP98,E04b,PRS16]. For some positive constant , we give a (3 2- )-approximation algorithm for the following problem: given a graph G_0=(V,E_0), find the shortest tour that visits every vertex at least once. This is a special case of the metric traveling salesman problem when the underlying metric is defined by shortest path distances in G_0. The result improves on the 3 2-approximation algorithm due to Christofides [C76] for this special case. Similar to Christofides, our algorithm finds a spanning tree whose cost is upper bounded by the optimum, then it finds the minimum cost Eulerian augmentation (or T-join) of that tree. The main difference is in the selection of the spanning tree. Except in certain cases where the solution of LP is nearly integral, we select the spanning tree randomly by sampling from a maximum entropy distribution defined by the linear programming relaxation. Despite the simplicity of the algorithm, the analysis builds on a variety of ideas such as properties of strongly Rayleigh measures from probability theory, graph theoretical results on the structure of near minimum cuts, and the integrality of the T-join polytope from polyhedral theory. Also, as a byproduct of our result, we show new properties of the near minimum cuts of any graph, which may be of independent interest.