ALGOTEL 2007 - Neuvièmes rencontres francophones sur les aspects algorithmiques de télécommunications collection |
 |
Conference papers
Non-Searchability of Random Scale-Free Graphs
Résumé : Nous nous intéressons à la complexité de recherche d'un noeud donné dans un graphe sans-échelle, en utilisant uniquement des informations locales. Pour les modèles généralisant les modèles de Barabási-Albert et de Cooper-Frieze, nous prouvons une borne inférieure de Omega(n^{1/2}) sur le nombre de sommets à visiter pour trouver le n-ième sommet inséré dans un modèle de connaissance locale faible.
Cited literature [8 references]
https://hal.inria.fr/inria-00176940
Contributor : David Coudert Connect in order to contact the contributor
Submitted on : Thursday, October 4, 2007 - 11:47:02 PM
Last modification on : Saturday, June 25, 2022 - 10:30:00 AM
Long-term archiving on: : Monday, September 24, 2012 - 1:11:04 PM
Contributor : David Coudert Connect in order to contact the contributor
Submitted on : Thursday, October 4, 2007 - 11:47:02 PM
Last modification on : Saturday, June 25, 2022 - 10:30:00 AM
Long-term archiving on: : Monday, September 24, 2012 - 1:11:04 PM
File
09-algotel2007final-hanusse.pd...
Publisher files allowed on an open archive