Models of random subtrees of a graph

DOI10.1214/23-ps22zbMath1527.60010arXiv2102.12738MaRDI QIDQ6183888

Publication date: 4 January 2024

Published in: Probability Surveys (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2102.12738

zbMATH Keywords

diffusion limited aggregation random generation random trees minimal spanning tree spanning trees lattice trees

Mathematics Subject Classification ID

Trees (05C05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Combinatorial probability (60C05) Functional limit theorems; invariance principles (60F17) Research exposition (monographs, survey articles) pertaining to probability theory (60-02)

Cites Work

Cutting down random trees
The Multiplicative Process
A Contribution to the Theory of Chromatic Polynomials
The height of increasing trees
Parking functions, empirical processes, and the width of rooted labeled trees
Otakar Borůvka on minimum spanning tree problem. Translation of both the 1926 papers, comments, history
Enumerations of lattice animals and trees
On the probability that a random subtree is spanning
Historical lattice trees
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
On the shortest spanning subtree of a graph and the traveling salesman problem
A new encoding of coalescent processes: applications to the additive and multiplicative cases
The cut-tree of large Galton-Watson trees and the Brownian CRT
Internal DLA in higher dimensions
Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation
Cutting down trees with a Markov chainsaw
Doob-Martin boundary of Rémy's tree growth chain
Fringe trees, Crump-Mode-Jagers branching processes and \(m\)-ary search trees
Asymptotic fringe distributions for general families of random trees
Enumeration of subtrees of trees
A characterization of the Tutte polynomial via combinatorial embeddings
Convergence of lattice trees to super-Brownian motion above the critical dimension
On the value of a random minimum spanning tree problem
Random generation of combinatorial structures from a uniform distribution
A combinatorial approach to matrix algebra
On Frieze's \(\zeta\) (3) limit for lengths of minimal spanning trees
Subdiffusive behavior of random walk on a random cluster
Choosing a spanning tree for the integer lattice uniformly
Internal diffusion limited aggregation
Matrix tree theorems
The scaling limit of lattice trees in high dimensions
The standard additive coalescent
Counting trees in a graph is \(\# \text{P}\)-complete
The depth first processes of Galton-Watson trees converge to the same Brownian excursion
Scaling limits of loop-erased random walks and uniform spanning trees
The scaling limits of the minimal spanning tree and invasion percolation in the plane
The scaling limit of the minimum spanning tree of the complete graph
Locally guided randomized elections in trees: The totally fair case
Uniform spanning forests
Conformal invariance of planar loop-erased random walks and uniform spanning trees.
Loop-erased random walks, spanning trees and Hamiltonian cycles
Solving the optimum communication spanning tree problem
A reverse Aldous-Broder algorithm
On the roots of the subtree polynomial
On the edge capacitated Steiner tree problem
Tree-decorated planar maps
Stationary harmonic measure and DLA in the upper half plane
On coding labeled trees
The loop-erased random walk and the uniform spanning tree on the four-dimensional discrete torus
Reversing the cut tree of the Brownian continuum random tree
The continuum limit of critical random graphs
Internal DLA and the Gaussian free field
Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
The lace expansion and its application. École d'Été de Probabilités de Saint-Flour XXXIV -- 2004.
On the upper critical dimension of lattice trees and lattice animals
Growing random uniform \(d\)-ary trees
The Potts model and the Tutte polynomial
Backbone scaling for critical lattice trees in high dimensions
Probability on Trees and Networks
Simulating Size-constrained Galton–Watson Trees
Off-critical lattice models and massive SLEs
Logarithmic fluctuations for internal DLA
50 Years of First-Passage Percolation
Phase transition for Parking blocks, Brownian excursion and coalescence
The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
The Differential Equations of Birth-and-Death Processes, and the Stieltjes Moment Problem
The Classification of Birth and Death Processes
Random cutting and records in deterministic and random trees
Generating random combinatorial objects
Random spanning tree
A nonlocal Monte Carlo algorithm for lattice trees
How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph
A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs
A new combinatorial representation of the additive coalescent
Subtrees of graphs
Simulations of lattice animals and trees
Boltzmann Samplers for the Random Generation of Combinatorial Structures
Algorithms for node‐weighted Steiner tree and maximum‐weight connected subgraph
On the computational complexity of the Jones and Tutte polynomials
One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
Unranking and ranking spanning trees of a graph
Building uniformly random subtrees
On the History of the Minimum Spanning Tree Problem
The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
Two Algorithms for Unranking Arborescences
Exact sampling with coupled Markov chains and applications to statistical mechanics
A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
Sampling random spanning trees faster than matrix multiplication
Reducibility among Combinatorial Problems
Faster Generation of Random Spanning Trees
An almost-linear time algorithm for uniform random spanning tree generation
Obtaining Optimalk-Cardinality Trees Fast
Fast Generation of Random Spanning Trees and the Effective Resistance Metric
On the Length of a Random Minimum Spanning Tree
Asymptotics of trees with a prescribed degree sequence and applications

This page was built for publication: Models of random subtrees of a graph