Exploring an unknown graph

We wish to explore all edges of an unknown directed, strongly connected gra ph. At each point, we have a map of ail nodes and edges we have visited, we can recognize these nodes and edges if we see them again, and we know how many unexplored edges emanate from each node we have visited, but we cannot tell where each leads until we traverse it. We wish to minimize the ratio of the total number of edges traversed divided by the optimum number of tra versals, had we known the graph. For Eulerian graphs, this ratio cannot be better than two, and two is achievable by a simple algorithm. In contrast, the ratio is unbounded when the deficiency of the graph (the number of edge s that have to be added to make it Eulerian) is unbounded. Our main result is an algorithm that achieves a bounded ratio when the deficiency is bounde d. (C) 1999 John Wiley & Sons, Inc.