×

zbMATH — the first resource for mathematics

Chip-firing games, potential theory on graphs, and spanning trees. (English) Zbl 1408.05089
Summary: We study the interplay between chip-firing games and potential theory on graphs, characterizing reduced divisors (\(G\)-parking functions) on graphs as the solution to an energy (or potential) minimization problem and providing an algorithm to efficiently compute reduced divisors. Applications include an “efficient bijective” proof of Kirchhoff’s matrix-tree theorem and a new algorithm for finding random spanning trees. The running times of our algorithms are analyzed using potential theory, and we show that the bounds thus obtained generalize and improve upon several previous results in the literature.

MSC:
05C57 Games on graphs (graph-theoretic aspects)
05C80 Random graphs (graph-theoretic aspects)
05C05 Trees
91A43 Games involving graphs
31C99 Generalizations of potential theory
PDF BibTeX XML Cite
Full Text: DOI arXiv