Skip to main content
Download PDF
- Main
Representing all minimum spanning trees with applications to counting and generation
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
For improved accessibility of PDF content, download the file to your device.
Enter the password to open this PDF file:
File name:
-
File size:
-
Title:
-
Author:
-
Subject:
-
Keywords:
-
Creation Date:
-
Modification Date:
-
Creator:
-
PDF Producer:
-
PDF Version:
-
Page Count:
-
Page Size:
-
Fast Web View:
-
Preparing document for printing…
0%