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

Tail bound for the minimal spanning tree of a complete graph

โœ Scribed by Jeong Han Kim; Sungchul Lee

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
202 KB
Volume
64
Category
Article
ISSN
0167-7152

No coin nor oath required. For personal study only.

โœฆ Synopsis

Suppose each edge of the complete graph K n is assigned a random weight chosen independently and uniformly from the unit interval [0; 1]. A minimal spanning tree is a spanning tree of K n with the minimum weight. It is easy to show that such a tree is unique almost surely. This paper concerns the number N n ( ) of vertices of degree in the minimal spanning tree of K n .

For a positive integer , Aldous (Random Struct. Algorithms 1 (1990) 383) proved that the expectation of N n ( ) is asymptotically ( )n, where ( ) is a function of given by explicit integrations. We develop an algorithm to generate the minimal spanning tree and Cherno -type tail bound for N n ( ).

๐Ÿ“œ SIMILAR VOLUMES

A self-stabilizing distributed algorithm
A self-stabilizing distributed algorithm for minimal spanning tree problem in a symmetric graph
โœ G. Antonoiu; P.K. Srimani ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 640 KB

Minimal Spanning Tree (MST) problem in an arbitrary undirected graph is an important problem in graph theory and has extensive applications. Numerous algorithms are available to compute an MST. Our purpose here is to propose a self-stabilizing distributed algorithm for the MST problem and to prove 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.