Graph Exploration: The Impact of a Distance Constraint

Stéphane Devismes, Yoann Dieudonné, Arnaud Labourel

A mobile agent, starting from a node $s$ of a simple undirected connected graph $G=(V,E)$, has to explore all nodes and edges of $G$ using the minimum number of edge traversals. To…