Fairest edge usage and minimum expected overlap for random spanning trees
2021
Abstract Random spanning trees of a graph G are governed by a corresponding probability mass distribution (or “law”), μ , defined on the set of all spanning trees of G . This paper addresses the problem of choosing μ in order to utilize the edges as “fairly” as possible. This turns out to be equivalent to minimizing, with respect to μ , the expected overlap of two independent random spanning trees sampled with law μ . In the process, we introduce the notion of homogeneous graphs. These are graphs for which it is possible to choose a random spanning tree so that all edges have equal usage probability. The main result is a deflation process that identifies a hierarchical structure of arbitrary graphs in terms of homogeneous subgraphs, which we call homogeneous cores. A key tool in the analysis is the spanning tree modulus, for which there exists an algorithm based on minimum spanning tree algorithms, such as Kruskal’s or Prim’s.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
8
References
0
Citations
NaN
KQI