Abstract
S. Koenig and Y. Smirnov. Graph Learning with a Nearest Neighbor Approach. In Conference on Computational Learning Theory (COLT), pages 19-28, 1996.Abstract: In this paper, we study how to traverse all edges of an unknown graph G=(V,E) that is bi-directed and strongly connected. This problem can be solved with a simple algorithm that traverses all edges at most twice, and no algorithm can do better in the worst case. Artificial Intelligence researchers, however, often use the following on-line nearest neighbor algorithm: repeatedly take a shortest path to the closest unexplored edge and traverse it. We prove bounds on the worst-case complexity of this algorithm. We show, for example, that its worst-case complexity is close to optimal for some classes of graphs, such as graphs with linear or star topology and dense graphs with edge lengths one. In general, however, its complexity can grow faster than linear in the sum of all edge lengths, although not faster than log(V) times the sum of all edge lengths.
Download the paper in gzipped postscript (large download time).
Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.
This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.