Please use this identifier to cite or link to this item:
|Title:||Average competitive ratios of on-line spanning trees|
|Authors:||Bao, F. |
|Keywords:||Analysis of algorithms|
Average case analysis
Minimum spanning trees
|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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Jan 19, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.