Rendezvous of Distance-Aware Mobile Agents in Unknown Graphs

Shantanu Das; Dariusz Dereniowski; Adrian Kosowski; Przemysław Uznański

doi:10.1007/978-3-319-09620-9_23

Rendezvous of Distance-Aware Mobile Agents in Unknown Graphs

Abstrakt

We study the problem of rendezvous of two mobile agents starting at distinct locations in an unknown graph. The agents have distinct labels and walk in synchronous steps. However the graph is unlabelled and the agents have no means of marking the nodes of the graph and cannot communicate with or see each other until they meet at a node. When the graph is very large we want the time to rendezvous to be independent of the graph size and to depend only on the initial distance between the agents and some local parameters such as the degree of the vertices, and the size of the agent’s label. It is well known that even for simple graphs of degree Δ, the rendezvous time can be exponential in Δ in the worst case. In this paper, we introduce a new version of the rendezvous problem where the agents are equipped with a device that measures its distance to the other agent after every step. We show that these distance-aware agents are able to rendezvous in any unknown graph, in time polynomial in all the local parameters such the degree of the nodes, the initial distance D and the size of the smaller of the two agent labels l = min (l1, l2). Our algorithm has a time complexity of O(Δ(D + logl)) and we show an almost matching lower bound of Ω(Δ(D + logl/logΔ)) on the time complexity of any rendezvous algorithm in our scenario. Further, this lower bound extends existing lower bounds for the general rendezvous problem without distance awareness.

Cytowania

8

CrossRef
0

Web of Science
1 2

Scopus

Autorzy (4)

Shantanu Das
- Aix-Marseille University and CNRS Le Laboratoire d’Informatique Fondamentale de Marseille
Dariusz Dereniowski prof. dr hab. inż.
Adrian Kosowski
- GANG Project, Inria Paris; Paris Diderot University and CNRS, France Le Laboratoire d'Informatique Algorithmique: Fondements et Applications
Przemysław Uznański
- LIF, Aix-Marseille University and CNRS Le Laboratoire d’Informatique Fondamentale de Marseille

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

pełna treść artykułu zobacz w serwisie zewnętrznym otwiera się w nowej karcie

Słowa kluczowe

Informacje szczegółowe

Kategoria:: Aktywność konferencyjna
Typ:: materiały konferencyjne indeksowane w Web of Science
Tytuł wydania:: Structural Information and Communication Complexity strony 295 - 310
ISSN:: 0302-9743
Język:: angielski
Rok wydania:: 2014
Opis bibliograficzny:: Das S., Dereniowski D., Kosowski A., Uznański P..: Rendezvous of Distance-Aware Mobile Agents in Unknown Graphs, W: Structural Information and Communication Complexity, 2014, Springer International Publishing,.
DOI:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/978-3-319-09620-9_23
Weryfikacja:: Politechnika Gdańska