RI | Publications | Graph Learning with a Nearest Neighbor Approach

Text only version of this site

Graph Learning with a Nearest Neighbor Approach
S. Koenig and Y. Smirnov
Proceedings of the Conference on Computational Learning Theory, 1996, pp. 19 - 28.

Jump to: Download | Abstract | Text Reference | BibTeX Reference

Download [Help]

Adobe portable document format (pdf) [148 KB]
Compressed postscript (ps.gz) [81 KB]

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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.

Text Reference

S. Koenig and Y. Smirnov, "Graph Learning with a Nearest Neighbor Approach," Proceedings of the Conference on Computational Learning Theory, 1996, pp. 19 - 28.

BibTeX Reference

@inproceedings{Koenig_1996_3862,
   author = "Sven Koenig and Y. Smirnov",
   title = "Graph Learning with a Nearest Neighbor Approach",
   booktitle = "Proceedings of the Conference on Computational Learning Theory",
   year = "1996",
   pages = "19 - 28"
}