Skip to search boxSkip to navigationSkip to main content

Deterministic rendezvous with different maps

  • Ashley Farrugia
    ,
  • Leszek Gąsieniec(corresponding author)
    ,
  • Łukasz Kuszner
    ,
  • Eduardo Pacheco
*Corresponding author for this work
  • Capgemini
    ,
  • University of Liverpool
    ,
  • University of Gdańsk
    ,
  • Oracle
Scholary Output:
Contribution to journal
Article
Peer-review

Open access

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.

Publication Information

Output type

Scholary Output:
Contribution to journal
Article
Peer-review

Original language

English (US)

Pages from-to (Number of pages)

Pages 49-59 (11 pages)

Journal (Volume, Issue Number)

Journal of Computer and System Sciences (Volume 106)

Publication milestones

  • Published - 12/2019

Publication status

Published - 12/2019

ISSN

0022-0000

Publication IDs

  • Scopus: 85068178648

Publication metrics

Metrics

Fractional count
1
Fractional count
0.25
Fractional count
3
Fractional count
0.75
Fractional count
1
Fractional count
1
SciVal
citations
1
SciVal
FWCI
0.21
SciVal
Author count
4
SciVal
Paper percentile
49
Scopus
citations

PlumX, opens in new tab

Citation count
2
Captures
5

Funding Details

Research partially supported by the Polish National Science Center grant DEC-2011/02/A/ST6/00201 and by Network Sciences and Technologies initiative at University of Liverpool. An extended abstract of this work appeared in Proc. 41st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2015) [29].☆ Research partially supported by the Polish National Science Center grant DEC-2011/02/A/ST6/00201 and by Network Sciences and Technologies initiative at University of Liverpool. An extended abstract of this work appeared in Proc. 41st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2015) [29]. We would like to thank the anonymous reviewers for valuable comments which led to improved quality and clarity of the presentation.☆ Research partially supported by the Polish National Science Center grant DEC-2011/02/A/ST6/00201 and by Network Sciences and Technologies initiative at University of Liverpool. An extended abstract of this work appeared in Proc. 41st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2015) [29].
FundersFunding number
Royal Liverpool University Hospital
-
NCN
DEC-2011/02/A/ST6/00201