An average case analysis of the minimum spanning tree heuristic for the power assignment problem

DOI10.1002/rsa.20831zbMath1430.68469OpenAlexW1832814332WikidataQ128812460 ScholiaQ128812460MaRDI QIDQ5236925

Jan-Kees C. W. van Ommeren, Richard J. Boucherie, Johann L. Hurink, Maurits de Graaf

Publication date: 16 October 2019

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20831

zbMATH Keywords

analysis of algorithmspoint processesapproximation algorithmsaverage case analysispower assignmentrange assignmentad-hoc networks

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items

Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments ⋮ Continuous approximation formulas for location problems

Cites Work

• On the connectivity threshold for general uniform metric spaces
• Asymptotics for Euclidean minimal spanning trees on random points
• A matching problem and subadditive Euclidean functionals
• The longest edge of the random minimal spanning tree
• The central limit theorem for Euclidean minimal spanning trees. I
• Power consumption in packet radio networks
• Asymptotics for weighted minimal spanning trees on random points
• The central limit theorem for weighted minimal spanning trees on random points
• Weak laws of large numbers in geometric probability
• Percolation and minimal spanning forests in infinite graphs
• A new look at independence
• Laws of large numbers in stochastic geometry with statistical applications
• On the Hardness of Range Assignment Problems
• On the number of leaves of a euclidean minimal spanning tree
• Probabilistic analysis of power assignments