A survey on relay placement with runtime and approximation guarantees

Lloyd, 2007, Relay node placement in wireless sensor networks, IEEE Transactions on Computers, 56, 134, 10.1109/TC.2007.250629 Srinivas, 2006, Mobile backbone networks—construction and maintenance, 166 Alon Efrat, Sándor P. Fekete, Poornananda R. Gaddehosur, Joseph S.B. Mitchell, Valentin Polishchuk, Jukka Suomela, Improved approximation algorithms for relay placement, in: Proc. 16th European Symposium on Algorithms, ESA 2008, 2008, pp. 356–367. X. Défago, A. Konagaya, Circle formation for oblivious anonymous mobile robots with no common sense of orientation, in: International Workshop on Principles of Mobile Computing, POMC, 2002, pp. 97–104. I. Chatzigiannakis, M. Markou, S. Nikoletseas, Distributed circle formation for anonymous oblivious robots, in: Workshop on Efficient and Experimental Algorithms, WEA, 2004, pp. 159–174. Yoann Dieudonné, Franck Petit, Self-stabilizing deterministic gathering, in: Algorithmic Aspects of Wireless Sensor Networks, 2009, pp. 230–241. Souissi, 2006, Gathering asynchronous mobile robots with inaccurate compasses, 333 Izumi, 2007, Gathering autonomous mobile robots with dynamic compasses: an optimal result, Distributed Computing, 298, 10.1007/978-3-540-75142-7_24 Prencipe, 2007, Impossibility of gathering by a set of autonomous mobile robots, Theoretical Computer Science, 384, 222, 10.1016/j.tcs.2007.04.023 Agmon, 2004, Fault-tolerant gathering algorithms for autonomous mobile robots, 1070 Cohen, 2005, Convergence properties of the gravitational algorithm in asynchronous robot systems, SIAM Journal on Computing, 34, 1516, 10.1137/S0097539704446475 Hideki Ando, Yoshinobu Suzuki, Masafumi Yamashita, Formation agreement problems for synchronous mobile robots with limited visibility, in: Proc. IEEE Syp. of Intelligent Control, 1995, pp. 453–460. Ando, 1999, Distributed memoryless point convergence algorithm for mobile robots with limited visibility, IEEE Transactions on Robotics and Automation, 15, 818, 10.1109/70.795787 Chen, 2000, Approximations for Steiner trees with minimum number of Steiner points, Journal of Global Optimization, 18, 17, 10.1023/A:1008384012064 Chen, 2001, Approximations for Steiner trees with minimum number of Steiner points, Theoretical Computer Science, 262, 83, 10.1016/S0304-3975(00)00182-1 Liu, 2006, On optimal placement of relay nodes for reliable connectivity in wireless sensor networks, Journal of Combinatorial Optimization, 11, 249, 10.1007/s10878-006-7140-y Weiyi Zhang, Guoliang Xue, Satyajayant Misra, Fault-tolerant relay node placement in wireless sensor networks: problems and algorithms, in: Proc. 26th Conference on Computer Communications, INFOCOM 2007, 2007, pp. 1649–1657. Bredin, 2005, Deploying sensor networks with guaranteed capacity and fault tolerance, 309 Yang Yang, Mingen Lin, Jinhui Xu, Yulai Xie, Minimum spanning tree with neighborhoods, in: Proc. 3rd Conference on Algorithmic Aspects in Information and Management, AAIM 2007, 2007, pp. 306–316. Ding-Zhu Du, Frank K. Hwang, An approach for proving lower bounds: solution of Gilbert–Pollak’s conjecture on Steiner ratio, in: Proc. 31st Symposium on Foundations of Computer Science, FOCS 1990, 1990, pp. 76–85. Mitchell, 1999, Guillotine subdivisions approximate polygonal subdivisions: a simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems, SIAM Journal on Computing, 28, 1298, 10.1137/S0097539796309764 auf der Heide, 2008, Local strategies for connecting stations by small robotic networks, vol. 268, 95, 10.1007/978-0-387-09655-1_9 Barbara Schneider, Lokale strategien zur aufrechterhaltung von kommunikation zwischen mobilen robotern, Master’s Thesis, University of Paderborn, 2008. Dynia, 2006, vol. 216, 137 Dynia, 2007, Local strategies for maintaining a chain of relay stations between an explorer and a base station, 260 Jaroslaw Kutylowski, Using mobile relays for ensuring connectivity in sparse networks, Dissertation, International Graduate School of Dynamic Intelligent Systems, December 2007. Kutyłowski, 2009, Optimal strategies for maintaining a chain of relays between an explorer and a base camp, Theoretical Computer Science, 410, 3391, 10.1016/j.tcs.2008.04.010 Philipp Brandes, Bastian Degener, Barbara Kempkes, Friedhelm Meyer auf der Heide, Building short chains of mobile robots locally with a bounded stepwidth, Preprint, 2010. wwwhni.uni-paderborn.de/alg/publikationen. Bastian Degener, Barbara Kempkes, Peter Kling, Friedhelm Meyer auf der Heide, A continuous, local strategy for constructing a short chain of mobile robots, in: 17th International Colloquium on Structural Information and Communication Complexity, 2010. Bastian Degener, Barbara Kempkes, Friedhelm Meyer auf der Heide, A local O(n2) gathering algorithm, in: SPAA’10: Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures, June 2010.