A Polynomial Time Algorithm for Exploring Unknown Graphs with Deficiency d
Stephen S. Kwek · 1997
We present an O(dn ~ +m)-time algorithm for exploring (constructing) an unknown strongly connected graph G with m edges and n vertices by traversing at most dn ~ -t- m edges. Here, d is the minimum number of edges needed to add to G to make it Eulerian. This parameter d was introduced by Deng and Papadimitriou in (Deng & Papadimitriou 1990) and is known as the deficiency of a graph. They showed that in the worst case, f] (d~m) edge traversals are required and gave an algorithm that achieves an upper bound of d°(d)m edge traversals. Subsequently, Albers and Henzinger (Albers & Henzinger 1997) gave an algorithm that achieves an upper bound of O (ded21°s din) edge traversals. Our bound is an improvement over these earlier bounds when d -~ ~(log n).