๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Counting Minimum Weight Spanning Trees

โœ Scribed by Andrei Z. Broder; Ernst W. Mayr

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
152 KB
Volume
24
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 with n vertices and m edges, our ลฝ ลฝ .. ลฝ . algorithm requires O M M n elementary operations, where M M n is the number of elementary operations needed to multiply n = n matrices. The w x previous best algorithm for this problem, due to Gavril 3 , required ลฝ ลฝ .. ลฝ O n M M n operations. Since the number of trees in a complete graph is n ny 2 , our algorithm, as well as Gavril's, might involve operations on numbers of this magnitude. Such operations are accounted as elementary . operations.

๐Ÿ“œ SIMILAR VOLUMES

On Minimum Edge Ranking Spanning Trees
On Minimum Edge Ranking Spanning Trees
โœ Kazuhisa Makino; Yushi Uno; Toshihide Ibaraki ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 243 KB

In this paper, we introduce the problem of computing a minimum edge ranking spanning tree (MERST); i.e., find a spanning tree of a given graph G whose edge ranking is minimum. Although the minimum edge ranking of a given tree can be computed in polynomial time, we show that problem MERST is NP-hard.

The Capacitated Minimum Spanning Tree
The Capacitated Minimum Spanning Tree
โœ K. M. Chandy; Tachen Lo ๐Ÿ“‚ Article ๐Ÿ“… 1973 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 386 KB

## Abstract The capacitated minimum spanning tree is an offspring of the minimum spanning tree and network flow problems. It has application in the design of multipoint linkages in elementary teleprocessing tree networks. Some theorems are used in conjunction with Little's branch and bound algorith

Average distance, minimum degree, and sp
Average distance, minimum degree, and spanning trees
โœ Dankelmann, Peter; Entringer, Roger ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 218 KB

The average distance ยต(G) of a connected graph G of order n is the average of the distances between all pairs of vertices of G, i.e., ยต(G) = ( n 2 ) -1 {x,y}โŠ‚V (G) d G (x, y), where V (G) denotes the vertex set of G and d G (x, y) is the distance between x and y. We prove that every connected graph

A note on bisecting minimum spanning tre
A note on bisecting minimum spanning trees
โœ W. M. Boyce; M. R. Garey; D. S. Johnson ๐Ÿ“‚ Article ๐Ÿ“… 1978 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 281 KB