TY - GEN
T1 - Deterministic rendezvous in restricted graphs
AU - Farrugia, Ashley
AU - Gąsieniec, Leszek
AU - Kuszner, Łukasz
AU - Pacheco, Eduardo
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2015.
PY - 2015
Y1 - 2015
N2 - In this paper we consider the problem of synchronous rendezvous in which two anonymous mobile entities (robots) A and B are expected to meet at the same time and point in a graph G = (V,E). Most of the work devoted to rendezvous in graphs assumes that robots have access to the same sets of nodes and edges, where the topology of connections may be initially known or unknown. In our work we assume the movement of robots is restricted by the topological properties of the graph space coupled with the intrinsic characteristics of robots preventing them from visiting certain edges in E. We consider three rendezvous models reflecting on restricted maneuverability of robots A and B. In Edge Monotonic Model each robot X ∈ {A,B} has weight wX and each edge in E has a weight restriction. Consequently, a robot X is only allowed to traverse edges with weight restrictions greater that wX. In the remaining two models graph G is unweighted and the restrictions refer to more arbitrary subsets of traversable nodes and edges. In particular, in Node Inclusive Model the set of nodes VX available to robot X, for X ∈ {A,B} satisfies the condition VA ⊆ VB or vice versa, and in Blind Rendezvous Model the relation between VA and VB is arbitrary. In each model we design and analyze efficient rendezvous algorithms. We conclude with a short discussion on the asynchronous case and related open problems.
AB - In this paper we consider the problem of synchronous rendezvous in which two anonymous mobile entities (robots) A and B are expected to meet at the same time and point in a graph G = (V,E). Most of the work devoted to rendezvous in graphs assumes that robots have access to the same sets of nodes and edges, where the topology of connections may be initially known or unknown. In our work we assume the movement of robots is restricted by the topological properties of the graph space coupled with the intrinsic characteristics of robots preventing them from visiting certain edges in E. We consider three rendezvous models reflecting on restricted maneuverability of robots A and B. In Edge Monotonic Model each robot X ∈ {A,B} has weight wX and each edge in E has a weight restriction. Consequently, a robot X is only allowed to traverse edges with weight restrictions greater that wX. In the remaining two models graph G is unweighted and the restrictions refer to more arbitrary subsets of traversable nodes and edges. In particular, in Node Inclusive Model the set of nodes VX available to robot X, for X ∈ {A,B} satisfies the condition VA ⊆ VB or vice versa, and in Blind Rendezvous Model the relation between VA and VB is arbitrary. In each model we design and analyze efficient rendezvous algorithms. We conclude with a short discussion on the asynchronous case and related open problems.
UR - http://www.scopus.com/inward/record.url?scp=84922032427&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84922032427&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-46078-8_16
DO - 10.1007/978-3-662-46078-8_16
M3 - Conference contribution
AN - SCOPUS:84922032427
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 189
EP - 200
BT - SOFSEM 2015
A2 - Italiano, Giuseppe F.
A2 - Margaria-Steffen, Tiziana
A2 - Pokorný, Jaroslav
A2 - Quisquater, Jean-Jacques
A2 - Wattenhofer, Roger
PB - Springer Verlag
T2 - 41st International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2015
Y2 - 24 January 2015 through 29 January 2015
ER -