Collision-free network exploration

作者：

Highlights：

• We minimize time of collision-free network exploration in synchronous model.

• We determine the exact time for tree exploration if agents know the tree.

• We provide asymptotically tight time for general network exploration with a map.

• For unknown trees, we give exploration algorithm using O(n2) time.

• For unknown general graphs, we give exploration algorithm using O(n5log⁡n) time.

摘要

•We minimize time of collision-free network exploration in synchronous model.•We determine the exact time for tree exploration if agents know the tree.•We provide asymptotically tight time for general network exploration with a map.•For unknown trees, we give exploration algorithm using O(n2) time.•For unknown general graphs, we give exploration algorithm using O(n5log⁡n) time.

论文关键词：Mobile agents,Network exploration,Synchronous agents

论文评审过程：Received 8 June 2014, Revised 25 November 2016, Accepted 26 November 2016, Available online 13 December 2016, Version of Record 27 February 2017.

论文官网地址：https://doi.org/10.1016/j.jcss.2016.11.008