COUNTING MINIMUM WEIGHT SPANNING-TREES

We present an algorithm for counting the number of minimum weight span ning trees, based on the fact that the generating function for the num ber of spanning trees of a given graph, by weight, can be expressed as a simple determinant. For a graph with n vertices and m edges, our al gorithm requires O(M(n)) elementary operations, where M(n) is the numb er of elementary operations needed to multiply n x n matrices. The pre vious best algorithm for this problem, due to Gavril [3]; required O(n M(n)) operations. (Since the number of trees in a complete graph is n( n-2), our algorithm, as well as Gavril's, might involve operations on numbers of this magnitude. Such operations are accounted as elementary operations.)