Optimal Constrained Graph Exploration

an unknown graph from a given start node with
either a tethered robot or a robot with
fuel tank of limited fuel capacity.
A tethered robot is constrained to remain within
a fixed distance from the start node, while a
fuel constrained robot must return for refuelling.
We present a linear time algorithm for exploring
the graph in the presence of these constraints.