Collision-Free Network Exploration

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

doi:10.1007/978-3-642-54423-1_30

Collision-Free Network Exploration

Abstract

A set of mobile agents is placed at different nodes of a n-node network. The agents synchronously move along the network edges in a collision-free way, i.e., in no round may two agents occupy the same node. In each round, an agent may choose to stay at its currently occupied node or to move to one of its neighbors. An agent has no knowledge of the number and initial positions of other agents. We are looking for the shortest possible time required to complete the collision-free network exploration, i.e., to reach a configuration in which each agent is guaranteed to have visited all network nodes and has returned to its starting location. We first consider the scenario when each mobile agent knows the map of the network, as well as its own initial position. We establish a connection between the number of rounds required for collision-free exploration and the degree of the minimum-degree spanning tree of the graph. We provide tight (up to a constant factor) lower and upper bounds on the collision-free exploration time in general graphs, and the exact value of this parameter for trees. For our second scenario, in which the network is unknown to the agents, we propose collision-free exploration strategies running in O(n^2) rounds for tree networks and in O(n^5 log(n)) rounds for general networks.

Citations

0

CrossRef
0

Web of Science
3

Scopus

Authors (6)

Jurek Czyzowicz
- Université du Québec en Outaouais Département d'informatique et d'ingénierie
Dariusz Dereniowski prof. dr hab. inż.
Leszek Gąsieniec
- University of Liverpool Department of Computer Science
Ralf Klasing
- Universit\'e de Bordeaux - Inria LaBRI, CNRS
Adrian Kosowski
- Universit\'e de Bordeaux - Inria LaBRI, CNRS
Dominik Pająk
- Universit\'e de Bordeaux - Inria LaBRI, CNRS

Cite as

Full text

full text is not available in portal

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

Keywords

Details

Category:: Conference activity
Type:: materiały konferencyjne indeksowane w Web of Science
Title of issue:: 11th Latin American Theoretical INformatics Symposium (LATIN) strony 342 - 354
Language:: English
Publication year:: 2014
Bibliographic description:: Czyzowicz J., Dereniowski D., Gąsieniec L., Klasing R., Kosowski A., Pająk ..: Collision-Free Network Exploration, W: 11th Latin American Theoretical INformatics Symposium (LATIN) , 2014, Springer Berlin Heidelberg,.
DOI:: Digital Object Identifier (open in new tab) 10.1007/978-3-642-54423-1_30
Verified by:: Gdańsk University of Technology