论文标题
在线图探索树木，单环图和仙人掌图
Online Graph Exploration on Trees, Unicyclic Graphs and Cactus Graphs
论文作者
论文摘要
我们研究了探索搜索者最初未知的无向加权图的所有顶点的问题。仅当搜索者访问其端点之一时，才会揭示图的边缘。从某个开始节点开始，搜索者的目标是访问图的每个顶点，然后尽可能短地返回巡回演出的开始节点。我们证明，最近的邻居算法在树上的竞争比率为$ n $，为$θ（\ log n）$，即没有比一般图表更好。此外，我们检查了以前未考虑的一系列参数的算法阻止，并证明它在独立图上具有3竞争性，以及$ 5/2+\ sqrt {2} \ sqrt {2} \ of 3.91 $ 3.91 $ -Competitive-Cactus图上的竞争者。这两个图类别最著名的下限是2。
We study the problem of exploring all vertices of an undirected weighted graph that is initially unknown to the searcher. An edge of the graph is only revealed when the searcher visits one of its endpoints. Beginning at some start node, the searcher's goal is to visit every vertex of the graph before returning to the start node on a tour as short as possible. We prove that the Nearest Neighbor algorithm's competitive ratio on trees with $n$ vertices is $Θ(\log n)$, i.e. no better than on general graphs. Furthermore, we examine the algorithm Blocking for a range of parameters not considered previously and prove it is 3-competitive on unicyclic graphs as well as $5/2+\sqrt{2}\approx 3.91$-competitive on cactus graphs. The best known lower bound for these two graph classes is 2.
