Different speeds suffice for rendezvous of two agents on arbitrary graphs
Date
2017Language
en
Keyword
Abstract
We consider the rendezvous problem for two robots on an arbitrary connected graph with n vertices and all its edges of length one. Two robots are initially located on two different vertices of the graph and can traverse its edges with different but constant speeds. The robots do not know their own speed. During their movement they are allowed to meet on either vertices or edges of the graph. Depending on certain conditions reflecting the knowledge of the robots we show that a rendezvous algorithm is always possible on a general connected graph. More specifically, we give new rendezvous algorithms for two robots as follows. (1) In unknown topologies. We provide a polynomial time rendezvous algorithm based on universal exploration sequences, assuming that n is known to the robots. (2) In known topologies. In this case we prove the existence of more efficient rendezvous algorithms by considering the special case of the two-dimensional torus. © Springer International Publishing AG 2017.
Collections
Related items
Showing items related by title, author, creator and subject.
-
Online graph exploration with advice
Dobrev, S.; Královič, R.; Markou, E. (2012)We study the problem of exploring an unknown undirected graph with non-negative edge weights. Starting at a distinguished initial vertex s, an agent must visit every vertex of the graph and return to s. Upon visiting a ... -
Knowledge distillation on neural networks for evolving graphs
Antaris S., Rafailidis D., Girdzijauskas S. (2021)Graph representation learning on dynamic graphs has become an important task on several real-world applications, such as recommender systems, email spam detection, and so on. To efficiently capture the evolution of a graph, ... -
GRATIS: A GRaph tool for information systems scientists
Vlachos V., Siklafidis T., Chantzi K. (2019)All technological, biological and social networks can be represented as graphs. Therefore, graphs are utilised in simulation-based studies of new algorithms and protocols in various scientific fields. This paper presents ...