*Stephen Kwek*

We present an *O*(*dn*^{2} + *m*)-time algorithm for exploring
(constructing) an unknown strongly connected
graph *G* with *m* edges and *n* vertices by
traversing at most *dn*^{2} + *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 * (*d*^{6}*d*^{2 log d}*m*) 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.