ID:14363
Type of Publication: Conference Proceedings
Authors: Pierre.Fraigniaud, Emmanuelle.Lebhar, Zvi Lotker
Title: Brief announcement: On augmented graph navigability
ConferenceName: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Year: 2006
Volume: 4167 NCS
Pages: 551 - 553
Abstract: It is known that graphs of doubling dimension O(log log n) can be augmented to become navigable. We show that for doubling dimension very much greater than log log n, an infinite family of graphs cannot be augmented to become navigable. Our proof uses a counting argument which enable us to consider any kind of augmentations. In particular we do not restrict our analysis to the case of symmetric distributions, nor to distributions for which the choice of the long range link at a node must be independent from the choices of long range links at other nodes. © Springer-Verlag Berlin Heidelberg 2006.
Keywords: Virtual reality;Probability distributions;Artificial intelligence;Computer science; ,
Last Updated: 9/4/2007 12:00:00 AM
Powered by Rami Palombo © 2005
Search in: Google Scholar  |  Scitation