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.
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.