Introduction and definitions
A graph
Press StartButton to launch applet:
Applet
In this applet the process of the constrained graph exploration is visualized.
Figure 1.
The most important stepts like "calling bDFS" (figure 1), "closest subtree" (figure 2), "merge trees" ( figure 3) etc. are highlighted by colorizing, and also displayed as text in the panel at the bottom.
Figure 2 
Figure 3 
After starting the exploration, the manipulation of the applet is limited. No further modification of the graph or of the input parameters are allowed (until the end of the exploration). This is necessary to assure that the algorithm runs correctly.
The algorithm terminates in two cases. The first case is, the graph has been completely explored (see figure 4). The second case is, all vertices that can be reached with the rope length have been explored (see figure 5).

Figure4 

Figure 5 
Algorithm
The first step is to run a depth first search (DFS) on the graph and stop, when the maximum rope length l has been reached. This algorithm is called bounded DFS (bDFS). Its weakness is that some vertices which are potentially reachable could remain unexplored, as shown in figure 6.
Figure 6
If the robot walks the path (s, 1, 2, ..., r1, r), the remaining three pink vertices cannot be reached, since the maximum rope length of r has been reached. But if the robot had walked the shorter path (s, r+1, r1, r) first, he could have visited the pink vertices as well.
Thus, the next step is to improve the algorithm and solve this problem. To do so, we invoke bDFS several times, each time starting from an appropriate vertex. During the exploration, the algorithm holds a list of vertexdisjoint subtrees T = {T_{1}, ..., T_{k}} with roots s_{1}, ..., s_{k}, from which the subtree T_{i} is chosen that is the closest to start vertex s. This subtree is being pruned: Subtrees T_{wj} (with root w_{j}) are cut off, if two conditions are satisfied:
 w_{j} has a minimum distance to s_{i} (minDist = αr/4)
 T_{wj} has a minimum depth (minDepth = αr/2)
After the pruning step the robot performs a DFS on the tree, and each time it encounters an incomplete explored vertex (i.e. a vertex that has incident edges which are unexplored), it runs a bDFS on that vertex. Vertices and edges that are newly discovered during the bDFS are used to create a new tree and appended to the list T. After exploration of T_{i}, all completely explored trees are removed from T, and trees with common vertices are merged. The algorithm stops when all trees in T have been explored and removed.
With this algorithm and parameters, the exploration is competetive.
References
Literatur:
[1]:  Duncan, Kobourov, Kumar. Optimal Constrained Graph Exploration. 2001. 