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

Average competitive ratios of on-line spanning trees

โœ Scribed by Feng Bao; Aohan Mei; Yoshihide Igarashi

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
284 KB
Volume
62
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

We study the average competitive ratio of on-line spanning trees with the same distribution of points in the Euclidean plane. We show a distribution of n points such that the average competitive ratio of on-line spanning trees by any on-line algorithm cannot be less than 4 In n -f . @ 1997 Elsevier Science B.V.

๐Ÿ“œ SIMILAR VOLUMES

On graphs with the maximum number of spa
On graphs with the maximum number of spanning trees
โœ Alexander K. Kelmans ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 814 KB

Let 3:; denote the set of simple graphs with n vertices and m edges, t ( G ) the number of spanning trees of a graph G , and F 2 H if t(K,\E(F))?t(K,\E(H)) for every s? max{u(F), u ( H ) } . We give a complete characterization of >-maximal (maximum) graphs in 3:; subject to m 5 n . This result conta

Parallel construction of optimal indepen
Parallel construction of optimal independent spanning trees on hypercubes
โœ Jinn-Shyong Yang; Shyue-Ming Tang; Jou-Ming Chang; Yue-Li Wang ๐Ÿ“‚ Article ๐Ÿ“… 2007 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 212 KB

The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages, including the increase of fault-tolerance and bandwidth. Thus, the designs of multiple ISTs on several classes of networks have been widely investigated. Tang et al. [S.-M. Tang,