Improved Lower Bound for Competitive Graph Exploration

Alexander Birx, Yann Disser, Alexander V. Hopp +1

We give an improved lower bound of 10/3 on the competitive ratio for the exploration of an undirected, edge-weighted graph with a single agent that needs to return to the starting…