# Online Graph Exploration on Trees, Unicyclic Graphs and Cactus Graphs

arXiv: https://arxiv.org/abs/2004.06690 · HTML: https://mlsanity.com/paper/2004.06690/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Apr 2020.

## Built on by (most cited first, 1 of 1)

- [Robustification of Online Graph Exploration Methods](https://mlsanity.com/paper/2112.05422/) (2021)

## Abstract (arXiv)

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 Theta(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+√2≈ 3.91-competitive on cactus graphs. The best known lower bound for these two graph classes is 2.