TY - GEN
T1 - Collision-free network exploration
AU - Czyzowicz, Jurek
AU - Dereniowski, Dariusz
AU - Gasieniec, Leszek
AU - Klasing, Ralf
AU - Kosowski, Adrian
AU - Paja̧k, Dominik
N1 - Funding Information:
Research partially supported by ANR project DISPLEXITY and by NCN under contract DEC-2011/02/A/ST6/00201. Dariusz Dereniowski has been partially supported by a scholarship for outstanding young researchers founded by the Polish Ministry of Science and Higher Education. The full text of the paper is available at: http://hal.inria.fr/hal-00736276.
PY - 2014
Y1 - 2014
N2 - 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 5logn) rounds for general networks.
AB - 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 5logn) rounds for general networks.
UR - http://www.scopus.com/inward/record.url?scp=84899956474&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84899956474&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-54423-1_30
DO - 10.1007/978-3-642-54423-1_30
M3 - Conference contribution
AN - SCOPUS:84899956474
SN - 9783642544224
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 342
EP - 354
BT - LATIN 2014
PB - Springer Verlag
T2 - 11th Latin American Theoretical Informatics Symposium, LATIN 2014
Y2 - 31 March 2014 through 4 April 2014
ER -