A Polynomial Time Algorithm for Exploring Unknown Graphs with Deficiency d

Stephen Kwek

We present an O(dn2 + m)-time algorithm for exploring (constructing) an unknown strongly connected graph G with m edges and n vertices by traversing at most dn2 + 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 and is known as the deficiency of a graph. Subsequently, Albers and Henzinger gave an algorithm that achieves an upper bound of O (d6d2 log dm) edge traversals. Our bound is an improvement over these earlier bounds.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.