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.68531OpenAlexW2890780660MaRDI 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
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Distributed algorithms (68W15)
Related Items
Ring exploration with myopic luminous robots, A structured methodology for designing distributed algorithms for mobile entities, Gathering problems for autonomous mobile robots with lights, Gathering robots in graphs: the central role of synchronicity, Bamboo garden trimming problem: priority schedulings, Distributed transformations of Hamiltonian shapes based on line moves, Arbitrary pattern formation on infinite regular tessellation graphs
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
