Counting Minimum Weight Spanning Trees
We present an algorithm for counting the number of minimum weight
spanning trees, based on the fact that the generating function for the
number of spanning trees of a given graph, by weight, can be expressed
as a simple determinant. For a graph on n vertices with m edges,
our algorithm requires O(M(n)) elementary
operations, where M(n) is the number of elementary operations
needed to multiply nxn matrices. The previous best algorithm
for this problem, due to Gavril (1987), required O(n M(n)) operations.
(Since the number of trees in a complete graph
is nn-2 our algorithm, as well as Gavril's, might involve
operations on numbers of this magnitude. Such operations are
accounted as elementary operations.)
