@article{4a464fb9ef524e0b89b53c9985daf825,
title = "An average case analysis of the minimum spanning tree heuristic for the power assignment problem",
abstract = "We present an average case analysis of the minimum spanning tree heuristic for the power assignment problem. The worst-case approximation ratio of this heuristic is 2.We show that in Euclidean d-dimensional space, when the vertex set consists of a set of i.i.d. uniform random independent, identically distributed random variables in [0,1]d , and the distance power gradient equals the dimension d, the minimum spanning tree-based power assignment converges completely to a constant depending only on d.",
keywords = "UT-Hybrid-D, Analysis of algorithms, Approximation algorithms, Average case analysis, Point processes, Power assignment, Range assignment, Ad-hoc networks",
author = "{de Graaf}, Maurits and Richard Boucherie and Hurink, {Johann L.} and {van Ommeren}, {Jan C.W.}",
note = "Wiley deal This research was supported by the Nederlands Organisation for Scientific Research (N.W.O.).",
year = "2019",
month = aug,
doi = "10.1002/rsa.20831",
language = "English",
volume = "55",
pages = "89--103",
journal = "Random Structures and Algorithms",
issn = "1042-9832",
publisher = "Wiley",
number = "1",
}