Improved Approximation Algorithms for Relay Placement

DOI10.1007/978-3-540-87744-8_30zbMath1158.68550arXiv1511.02525OpenAlexW2569071700MaRDI QIDQ3541099

Valentin Polishchuk, Joseph S. B. Mitchell, Sándor P. Fekete, Jukka Suomela, Poornananda R. Gaddehosur, Alon Efrat

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

zbMATH Keywords

approximation algorithmswireless networkssensor networkspolynomial-time approximation scheme (PTAS)relaysSteiner minimum spanning tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Discrete location and assignment (90B80) Distributed systems (68M14) Approximation algorithms (68W25)

Related Items (5)

Improved approximation algorithms for single-tiered relay placement ⋮ Relay placement for fault tolerance in wireless networks in higher dimensions ⋮ A survey on relay placement with runtime and approximation guarantees ⋮ Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs ⋮ Exploring and Triangulating a Region by a Swarm of Robots

This page was built for publication: Improved Approximation Algorithms for Relay Placement