ALGORITHMS FOR EXPLORING AN UNKNOWN GRAPH
Margrit Betke · DSpace@MIT (Massachusetts Institute of Technology) · 1992
We consider the problem of exploring an unknown strongly connected directed graph. We use the exploration model introduced by Deng and Papadimitriou [DP90]. An explorer follows the edges of an unknown graph until she has seen the edges and vertices of the graph. The explorer does not know how many vertices and edges the graph has, or how the vertices are connected. At each vertex the explorer can see how many edges are leaving the vertex, but she does not know where they lead to. She chooses one such edge and explores it by traversing it. Deng and Papadimitriou [DP90] have shown that the graph exploration problem for graphs that are very similar to Eulerian graphs can be solved efficiently. They introduce the notion of deficiency for such graphs to measure the "distance" from being Eulerian and give algorithms that solve the exploration problem for deficiency-one and bounded deficiency graphs. We review