Details

Autor(en) / Beteiligte

• Degener, Bastian
• Kempkes, Barbara
• auf der Heide, Friedhelm

Titel

A local O(n 2 ) gathering algorithm

Ist Teil von

• Proceedings of the twenty-second annual ACM symposium on parallelism in algorithms and architectures, 2010, p.217-223

Ort / Verlag

ACM

Erscheinungsjahr

2010

Link zum Volltext

Quelle

ACM Digital Library Complete

Beschreibungen/Notizen

• The gathering problem, where $n$ autonomous robots with restricted capabilities are required to meet in a single point of the plane, is widely studied. We consider the case that robots are limited to see only robots within a bounded vicinity and present an algorithm achieving gathering in O ( n 2 ) rounds in expectation. A round consists of a movement of all robots, in random order. All previous algorithms with a proven time bound assume global view on the configuration of all robots.