Please use this identifier to cite or link to this item: https://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
Citation: 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)

44
checked on Jun 23, 2022

Google ScholarTM

Check


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