Exploring an unknown graph

✍ Scribed by Deng, Xiaotie; Papadimitriou, Christos H.

• Book ID: 101228214
• Publisher: John Wiley and Sons
• Year: 1999
• Tongue: English
• Weight: 436 KB
• Volume: 32
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199911)32:3<265::aid-jgt6>3.0.co;2-8

✦ Synopsis

We wish to explore all edges of an unknown directed, strongly connected graph. At each point, we have a map of all 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 traversals, 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 edges 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 bounded.