Collision-free network exploration

Jurek Czyzowicz; Dariusz Dereniowski; Leszek Gąsieniec; Ralf Klasing; Adrian Kosowski; Dominik Pająk

doi:10.1016/j.jcss.2016.11.008

Collision-free network exploration

Abstract

Mobile agents start at different nodes of an n-node network. The agents synchronously move along the network edges in a collision-free way, i.e., in no round two agents may occupy the same node. An agent has no knowledge of the number and initial positions of other agents. We are looking for the shortest time required to reach a configuration in which each agent has visited all nodes and returned to its starting location. In the scenario when each mobile agent knows the map of the network, we provide tight (up to a constant factor) lower and upper bounds on the collision-free exploration time in arbitrary graphs, and the exact bound for the trees. In the second scenario, where the network is unknown to the agents, we propose collision-free exploration strategies running in O(n^2) rounds in tree networks and in O(n^5log⁡n) rounds in networks with an arbitrary topology.

Citations

1

CrossRef
0

Web of Science
3

Scopus

Authors (6)

Jurek Czyzowicz
- Université du Québec en Outaouais
Dariusz Dereniowski prof. dr hab. inż.
Leszek Gąsieniec
- University of Liverpool
Ralf Klasing
- Université de Bordeaux CNRS, LaBRI
Adrian Kosowski
- Paris-Rocquencourt IAFA, Inria
Dominik Pająk
- Wrocław University of Science and Technology Department of Computer Science

Cite as

Full text

download paper

downloaded 23 times

Publication version: Accepted or Published Version
DOI:: Digital Object Identifier (open in new tab) 10.1016/j.jcss.2016.11.008
License: Copyright (2016 Elsevier B.V)

full content of the article see on external site open in new tab

Keywords

ALGORYTMY ROZPROSZONE,TEORIA GRAFÓW

Details

Category:: Articles
Type:: artykuł w czasopiśmie wyróżnionym w JCR
Published in:: JOURNAL OF COMPUTER AND SYSTEM SCIENCES no. 8, pages 70 - 81,
ISSN: 0022-0000
Language:: English
Publication year:: 2017
Bibliographic description:: Czyzowicz J., Dereniowski D., Gąsieniec L., Klasing R., Kosowski A., Pająk D.: Collision-free network exploration// JOURNAL OF COMPUTER AND SYSTEM SCIENCES. -Vol. 8, (2017), s.70-81
DOI:: Digital Object Identifier (open in new tab) 10.1016/j.jcss.2016.11.008
Verified by:: Gdańsk University of Technology