𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The competitiveness of randomized algorithms for on-line Steiner tree and on-line spanning tree problems

✍ Scribed by Ying Teh Tsai; Chuan Yi Tang

Book ID
107766124
Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
373 KB
Volume
48
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Average competitive ratios of on-line sp
Average competitive ratios of on-line spanning trees
✍ Feng Bao; Aohan Mei; Yoshihide Igarashi πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 284 KB

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

A note on genetic algorithms for degree-
A note on genetic algorithms for degree-constrained spanning tree problems
✍ Zhou, Gengui; Gen, Mitsuo πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 58 KB πŸ‘ 2 views

The degree-constrained spanning tree problem is of high practical importance. Up to now, there are few effective algorithms to solve this problem because of its NP-hard complexity. In this paper, we present a new approach to solve this problem by using genetic algorithms and computational results to

On-Line Coloring of Sparse Random Graphs
On-Line Coloring of Sparse Random Graphs and Random Trees
✍ Boris Pittel; Robert S. Weishaar πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 164 KB

The performance of the greedy coloring algorithm ''first fit'' on sparse random graphs G and on random trees is investigated. In each case, approximately n, c r n log log n colors are used, the exact number being concentrated almost surely on at 2 most two consecutive integers for a sparse random gr