Randomization Helps in Online Graph Exploration: Breaking the Deterministic Lower Bound on Cycles

Júlia Baligács, Jan Hązła, Lena Volk

In online graph exploration, introduced by Kalyanasundaram and Pruhs (1994), an agent must visit all vertices of an initially unknown weighted graph and return to its starting posi…