A Doubling Dimension Threshold Θ(loglogn) for Augmented Graph Navigability

详细信息    查看全文

• 作者：Pierre Fraigniaud ; Emmanuelle Lebhar ; Zvi Lotker
• 关键词：doubling dimension ; small world ; greedy routing
• 刊名：Lecture Notes in Computer Science
• 出版年：2006
• 出版时间：2006
• 年：2006
• 卷：4168
• 期：1
• 页码：376-386
• 全文大小：525 KB
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

In his seminal work, Kleinberg showed how to augment meshes using random edges, so that they become navigable; that is, greedy routing computes paths of polylogarithmic expected length between any pairs of nodes. This yields the crucial question of determining wether such an augmentation is possible for all graphs. In this paper, we answer negatively to this question by exhibiting a threshold on the doubling dimension, above which an infinite family of graphs cannot be augmented to become navigable whatever the distribution of random edges is. Precisely, it was known that graphs of doubling dimension at most O(loglogn) are navigable. We show that for doubling dimension ?loglogn, an infinite family of graphs cannot be augmented to become navigable. Finally, we complete our result by studying the special case of square meshes, that we prove to always be augmentable to become navigable.