Exploration of Constantly Connected Dynamic Graphs Based on Cactuses
Exploration of Constantly Connected Dynamic Graphs Based on Cactuses
复制标题
基于Cactuses的常连通动态图探索
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
A. Wade
中科院分区：
文献类型：
--
作者：
D. Ilcinkas;R. Klasing;A. Wade
我们研究了一类动态网络的移动实体(代理)的探索问题，即常连通动态图。这个问题已经在代理知道图的动态并且基础图是n个顶点的环的情况下进行了研究[5]。在这篇文章中，我们考虑同样的问题，我们假设基础图是仙人掌图(其中任何两个简单圈至多有一个公共顶点的连通图)。我们提出了一个算法，允许代理在至多(2^{O(Sqrt{logn})}n)个时间单位内搜索这些动态图。证明了该算法的下界为(2^{Omega(Sqrt{logn})}n)个时间单位。
We study the problem of exploration by a mobile entity (agent) of a class of dynamic networks, namely constantly connected dynamic graphs. This problem has already been studied in the case where the agent knows the dynamics of the graph and the underlying graph is a ring of n vertices [5]. In this paper, we consider the same problem and we suppose that the underlying graph is a cactus graph (a connected graph in which any two simple cycles have at most one vertex in common). We propose an algorithm that allows the agent to explore these dynamic graphs in at most (2^{O(sqrt{log n})} n) time units. We show that the lower bound of the algorithm is (2^{Omega(sqrt{log n})} n) time units.