Chip-firing games, potential theory on graphs, and spanning trees

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:120

Article

Baker, Matthew¹  Shokrieh, Farbod¹ 

[1] Georgia Inst Technol, Atlanta, GA 30332 USA

关键词: Chip-firing;    Potential theory;    Energy pairing;    Reduced divisors;    Matrix-tree theorem;    Random spanning trees;   

DOI  :  10.1016/j.jcta.2012.07.011

来源: Elsevier

【 摘 要 】

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 Kirchhoffs 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. (C) 2012 Elsevier Inc. All rights reserved.

【 授权许可】

Free