  Kirchhoff's matrix-tree theorem states that the number of spanning trees of a
graph G is equal to the value of the determinant of the reduced Laplacian of
$G$. We outline an efficient bijective proof of this theorem, by studying a
canonical finite abelian group attached to $G$ whose order is equal to the
value of same matrix determinant. More specifically, we show how one can
efficiently compute a bijection between the group elements and the spanning
trees of the graph. The main ingredient for computing the bijection is an
efficient algorithm for finding the unique $G$-parking function (reduced
divisor) in a linear equivalence class defined by a chip-firing game. We also
give applications, including a new and completely algebraic algorithm for
generating random spanning trees. Other applications include algorithms related
to chip-firing games and sandpile group law, as well as certain algorithmic
problems about the Riemann-Roch theory on graphs.
