A survey on relay placement with runtime and approximation guarantees

DOI10.1016/j.cosrev.2010.09.005zbMath1298.68292OpenAlexW2027533686MaRDI QIDQ465673

Bastian Degener, Friedhelm Meyer auf der Heide, Barbara Kempkes, Sándor P. Fekete

Publication date: 24 October 2014

Published in: Computer Science Review (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cosrev.2010.09.005

zbMATH Keywords

mobile robotslocal algorithmsrelay placementrobot formations

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Distributed systems (68M14) Approximation algorithms (68W25) Artificial intelligence for robotics (68T40)

Related Items

Exploring and Triangulating a Region by a Swarm of Robots

Cites Work

• Unnamed Item
• Energy-efficient strategies for building short chains of mobile robots locally
• Optimal strategies for maintaining a chain of relays between an explorer and a base camp
• Impossibility of gathering by a set of autonomous mobile robots
• On optimal placement of relay nodes for reliable connectivity in wireless sensor networks
• Gathering Autonomous Mobile Robots with Dynamic Compasses: An Optimal Result
• Improved Approximation Algorithms for Relay Placement
• A Continuous, Local Strategy for Constructing a Short Chain of Mobile Robots
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Relay Node Placement in Wireless Sensor Networks
• Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems
• Minimum Spanning Tree with Neighborhoods
• Approximations for Steiner trees with minimum number of Steiner points
• Approximations for Steiner trees with minimum number of Steiner points