A survey on relay placement with runtime and approximation guarantees

DOI10.1016/J.COSREV.2010.09.005MaRDI QIDQ465673zbMATHOpenAlexFDO

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

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) Approximation algorithms (68W25) Artificial intelligence for robotics (68T40) Distributed systems (68M14)

Recommendations

• Improved approximation algorithms for single-tiered relay placement
• SOFSEM 2006: Theory and Practice of Computer Science
• Relays: a new approach for the finite departure problem in overlay networks
• Approximation Algorithms for Constrained Relay Node Placement in Energy Harvesting Wireless Sensor Networks
• On optimal placement of relay nodes for reliable connectivity in wireless sensor networks
• scientific article; zbMATH DE number 1688370

Cites work

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

Cited in

(5)

• Novel hybrid heuristics for an extension of the dynamic relay deployment problem over disaster areas
• Optimal strategies for maintaining a chain of relays between an explorer and a base camp
• Optimal placement of UV-based communications relay nodes
• Relays: a new approach for the finite departure problem in overlay networks
• Exploring and triangulating a region by a swarm of robots

This page was built for publication: A survey on relay placement with runtime and approximation guarantees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q465673)