Generalized loop‐erased random walks and approximate reachability

DOI10.1002/rsa.20460zbMath1303.05181OpenAlexW2117405272MaRDI QIDQ5409862

Igor Pak, Igor Gorodezky

Publication date: 15 April 2014

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20460

zbMATH Keywords

reliabilityreachabilityhypertreeloop-erased random walkperfect sampling

Mathematics Subject Classification ID

Hypergraphs (05C65) Random walks on graphs (05C81)

Related Items

Spanning trees in random regular uniform hypergraphs, Abelian networks. III: The critical group, Random walks and Laplacians on hypergraphs: when do they match?, Infinite weighted graphs with bounded resistance metric, Normal Approximation for Functions of Hidden Markov Models, Unnamed Item, Abelian Networks I. Foundations and Examples, A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability, Approximately counting bases of bicircular matroids

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sum complexes---a new family of hypertrees
• Higher-dimensional tree structures. I
• Enumeration of \({\mathbb{Q}}\)-acyclic simplicial complexes
• Two remarks concerning balanced matroids
• Monte-Carlo algorithms for the planar multiterminal network reliability problem
• Random generation of combinatorial structures from a uniform distribution
• Generating random elements of finite distributive lattices
• The facet ideal of a simplicial complex
• Percolation on finite graphs and isoperimetric inequalities.
• Conformal invariance of planar loop-erased random walks and uniform spanning trees.
• Loop-erased random walks, spanning trees and Hamiltonian cycles
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
• Coloured Loop-Erased Random Walk on the Complete Graph
• Simplicial matrix-tree theorems
• Random spanning tree
• Calculating bounds on reachability and connectedness in stochastic networks
• Monte-Carlo approximation algorithms for enumeration problems
• The Complexity of Enumeration and Reliability Problems
• A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
• Branching processes and random hypertrees
• Exact sampling with coupled Markov chains and applications to statistical mechanics
• Percolation on Finite Cayley Graphs
• Properties and characterizations of k ‐trees
• Generating a random sink-free orientation in quadratic time