Improved Approximation Algorithms for Relay Placement
From MaRDI portal
Publication:3541099
DOI10.1007/978-3-540-87744-8_30zbMath1158.68550arXiv1511.02525MaRDI QIDQ3541099
Sándor P. Fekete, Joseph S. B. Mitchell, Alon Efrat, Valentin Polishchuk, Jukka Suomela, Poornananda R. Gaddehosur
Publication date: 25 November 2008
Published in: ACM Transactions on Algorithms, Algorithms - ESA 2008 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1511.02525
approximation algorithms; wireless networks; sensor networks; polynomial-time approximation scheme (PTAS); relays; Steiner minimum spanning tree
68R10: Graph theory (including graph drawing) in computer science
90B80: Discrete location and assignment
68M14: Distributed systems
68W25: Approximation algorithms