Skip to main content
eScholarship
Open Access Publications from the University of California

Representing all minimum spanning trees with applications to counting and generation

  • Author(s): Eppstein, David
  • et al.
Abstract

We show that for any edge-weighted graph G there is an equivalent graph EG such that the minimum spanning trees of G correspond one-for-one with the spanning trees of EG. The equivalent graph can be constructed in the time O(m + n log n) given a single minimum spanning tree of G. As a consequence we can count the minimum spanning trees of G in time O(m + n^2.376), generate a random minimum spanning tree in time O(mn), and list all minimum spanning trees in time O(m + n log n + k) where k denotes the number of minimum spanning trees generated. We also discuss similar equivalent graph constructions for shortest paths, minimum cost flows, and bipartite matching.

Main Content
Current View