Polylogarithmic-overhead piecemeal graph exploration

Baruch Awerbuch, Stephen G. Kobourov

Research output: Contribution to conferencePaperpeer-review

10 Scopus citations


We introduce a new traversal technique in the context of piecemeal exploration of unknown graphs. The problem of learning a graph via piecemeal exploration requires a robot to create a complete map of its environment, subject to two constraints. First, it cannot jump between non-adjacent vertices in one time step and second, it must return to a fixed starting point every so often. This paper presents the recursive piecemeal search (RPS) strategy together with an algorithm for the above problem. We are able to achieve O(log2 n) overhead (where n is the number of vertices), improving on previous results of Awerbuch, Betke, Rivest, and Singh which require O(nε) overhead. The graph is discovered via the recursive piecemeal search, which can be viewed as a combination of breadth-first and depth-first passes. The construction of RPS trees relies on the concept of sparse neighborhood covers and captures nicely the nature of the graph exploration problem.

Original languageEnglish (US)
Number of pages7
StatePublished - 1998
EventProceedings of the 1998 11th Annual Conference on Computational Learning Theory - Madison, WI, USA
Duration: Jul 24 1998Jul 26 1998


OtherProceedings of the 1998 11th Annual Conference on Computational Learning Theory
CityMadison, WI, USA

ASJC Scopus subject areas

  • Computational Mathematics


Dive into the research topics of 'Polylogarithmic-overhead piecemeal graph exploration'. Together they form a unique fingerprint.

Cite this