Online graph exploration algorithms for cycles and trees by multiple searchers
Online graph exploration algorithms for cycles and trees by multiple searchers
复制标题
DOI：
10.1007/s10878-012-9571-y
复制
发表时间：
2012-12
影响因子：
1
通讯作者：
Yuya Higashikawa;N. Katoh;S. Langerman;Shin-ichi Tanigawa
中科院分区：
文献类型：
--
作者：
Yuya Higashikawa;N. Katoh;S. Langerman;Shin-ichi Tanigawa
本文讨论了多搜索器的在线图探索问题。图表上的信息在网上提供。随着探索的进行，搜索者在图上获得更多的信息。假设搜索者之间有一个合适的通信模型，搜索者就可以共享环境信息。因此，搜索者必须根据搜索者迄今为止获得的图上的部分信息来决定下一个访问哪个顶点。我们假设所有的搜索者最初都是从原始顶点开始探索的，目标是每个顶点至少被一个搜索者访问，所有的搜索者最终都返回到原始顶点。目标是尽量缩短实现目标的时间。我们研究了周期和树的情况。对于前者，我们给出了一个基于竞争比的最优在线探索算法，对于后者，我们也给出了一个在线探索算法，它是贪婪算法中的最优算法。
This paper deals with online graph exploration problems by multiple searchers. The information on the graph is given online. As the exploration proceeds, searchers gain more information on the graph. Assuming an appropriate communication model among searchers, searchers can share the information about the environment. Thus, a searcher must decide which vertex to visit next based on the partial information on the graph gained so far by searchers. We assume that all searchers initially start the exploration at the origin vertex, and the goal is that each vertex is visited by at least one searcher and all searchers finally return to the origin vertex. The objective is to minimize the time when the goal is achieved. We study the case of cycles and trees. For the former, we give an optimal online exploration algorithm in terms of competitive ratio, and for the latter, we also give an online exploration algorithm which is optimal among greedy algorithms.