Deterministic rendezvous with different maps

Ashley Farrugia , Leszek Gąsieniec , Łukasz Kuszner , Eduardo Pacheco

Abstract

We consider a rendezvous problem in which two identical anonymous mobile entities A and B, called later robots, are asked to meet at some node in the network modelled by an arbitrary undirected graph G = (V, E). Most of the work devoted to rendezvous in graphs assumes robots have access to the same sets of nodes and edges, and the topology of connections is either known or unknown to the robots. In this work we assume that each robot may access only specific nodes and edges in G of which full map is given to the robot in advance. We consider three variants of rendezvous differentiated by the level of restricted maneuverability of robots in both synchronous and asynchronous models of computation. In each adopted variant and model of computation we study feasibility of rendezvous, and if rendezvous is possible we propose the relevant algorithms and discuss their efficiency.
Author Ashley Farrugia
Ashley Farrugia,,
-
, Leszek Gąsieniec
Leszek Gąsieniec,,
-
, Łukasz Kuszner (FMPI / II)
Łukasz Kuszner,,
- Institute of Informatics
, Eduardo Pacheco
Eduardo Pacheco,,
-
Journal seriesJournal of Computer and System Sciences, ISSN 0022-0000, e-ISSN 1090-2724, (N/A 100 pkt)
Issue year2019
Vol106
Pages49-59
Publication size in sheets0.5
Keywords in Englishdistributed algorithm, mobile agents, Rendezvous
ASJC Classification1703 Computational Theory and Mathematics; 1705 Computer Networks and Communications; 2604 Applied Mathematics; 2614 Theoretical Computer Science
DOIDOI:10.1016/j.jcss.2019.06.001
URL https://doi.org/10.1016/j.jcss.2019.06.001
Languageen angielski
Score (nominal)100
Score sourcejournalList
ScoreMinisterial score = 100.0, 16-02-2020, ArticleFromJournal
Publication indicators WoS Citations = 0; Scopus SNIP (Source Normalised Impact per Paper): 2018 = 1.334; WoS Impact Factor: 2018 = 1.129 (2) - 2018=1.739 (5)
Citation count*8 (2020-03-20)
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back
Confirmation
Are you sure?