Characterizing the computational power of mobile robots on graphs and implications for the Euclidean plane
From MaRDI portal
Publication:1627966
DOI10.1016/j.ic.2018.09.010zbMath1407.68531MaRDI QIDQ1627966
Gabriele Di Stefano, Mattia D'Emidio, Daniele Frigioni, Alfredo Navarra
Publication date: 3 December 2018
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2018.09.010
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68R10: Graph theory (including graph drawing) in computer science
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
68W15: Distributed algorithms
Related Items
Cites Work
- Computing on rings by oblivious robots: a unified approach for different tasks
- A unified approach for gathering and exclusive searching on rings under weak assumptions
- Gathering of oblivious robots on infinite grids with minimum traveled distance
- Gathering of asynchronous robots with limited visibility
- Synchronous robots vs asynchronous lights-enhanced robots on graphs
- Explore and repair graphs with black holes using mobile entities
- Autonomous mobile robots with lights
- Arbitrary pattern formation by asynchronous, anonymous, oblivious robots
- Remembering without memory: tree exploration by asynchronous oblivious robots
- Locating and repairing faults in a network with mobile agents
- Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring
- Anonymous graph exploration with binoculars
- Gathering of robots on meeting-points: feasibility and optimal resolution algorithms
- How to meet when you forget: log-space rendezvous in arbitrary graphs
- Exploring an unknown dangerous graph using tokens
- Gathering on rings under the look-compute-move model
- Computing without communicating: ring exploration by asynchronous oblivious robots
- Optimal gathering of oblivious robots in anonymous graphs and its application on trees and rings
- Graph decomposition for memoryless periodic exploration
- Gathering six oblivious robots on anonymous symmetric rings
- Gathering asynchronous oblivious mobile robots in a ring
- About Ungatherability of Oblivious and Asynchronous Robots on Anonymous Rings
- Gathering an Even Number of Robots in an Odd Ring without Global Multiplicity Detection
- Optimal Probabilistic Ring Exploration by Semi-synchronous Oblivious Robots
- Design and Analysis of Distributed Algorithms
- Leader Election Problem versus Pattern Formation Problem
- Distributed Anonymous Mobile Robots: Formation of Geometric Patterns
- Asynchronous Pattern Formation by Anonymous Oblivious Mobile Robots
- On the computational power of oblivious robots
- Pattern Formation by Oblivious Asynchronous Mobile Robots
- Distributed Models and Algorithms for Mobile Robot Systems
- Distributed Computing – IWDC 2005
- Fault-tolerant complete visibility for asynchronous robots with lights under one-axis agreement
