𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A parallel algorithm for the enumeration of the spanning trees of a graph

✍ Scribed by Shao-Wen Mai; D.J. Evans

Publisher
Elsevier Science
Year
1984
Tongue
English
Weight
450 KB
Volume
1
Category
Article
ISSN
0167-8191

No coin nor oath required. For personal study only.

✦ Synopsis

As is well known, the strategy of divide-and-conquer is widely used in problem solving. The method of partitioning is also a fundamental strategy for the design of a parallel algorithm. The problem of enumerating the spanning trees of a graph arises in several contexts such as computer-aided design and computer networks. A parallel algorithm for solving the problem is presented in this paper. It is based on the principle of the inclusion and exclusion of sets, and not directly based on the partitioning of the graph itself. The results of the preliminary experiments on a MIMD system appear promising.

πŸ“œ SIMILAR VOLUMES

A Parallel Algorithm for Computing Minim
A Parallel Algorithm for Computing Minimum Spanning Trees
✍ D.B. Johnson; P. Metaxas πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 840 KB

We present a simple and implementable algorithm that computes a minimum spanning tree of an undirected weighted graph \(G=(V, E)\) of \(n=|V|\) vertices and \(m=|E|\) edges on an EREW PRAM in \(O\left(\log ^{3 / 2} n\right)\) time using \(n+m\) processors. This represents a substantial improvement i

The number of spanning trees of a graph
The number of spanning trees of a graph
✍ Jianxi Li; Wai Chee Shiu; An Chang πŸ“‚ Article πŸ“… 2010 πŸ› Elsevier Science 🌐 English βš– 387 KB

In this paper, we present some sharp upper bounds for the number of spanning trees of a connected graph in terms of its structural parameters such as the number of vertices, the number of edges, maximum vertex degree, minimum vertex degree, connectivity and chromatic number.