Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/129710
Title: Average competitive ratios of on-line spanning trees
Authors: Bao, F. 
Mei, A.
Igarashi, Y.
Keywords: Analysis of algorithms
Average case analysis
Competitive ratios
Minimum spanning trees
Issue Date: 28-May-1997
Source: Bao, F., Mei, A., Igarashi, Y. (1997-05-28). Average competitive ratios of on-line spanning trees. Information Processing Letters 62 (4) : 213-216. ScholarBank@NUS Repository.
Abstract: 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 1/4 In n - 1/2. © 1997 Elsevier Science B.V.
Source Title: Information Processing Letters
URI: http://scholarbank.nus.edu.sg/handle/10635/129710
ISSN: 00200190
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

9
checked on Jan 19, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.