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.
Type de document :
Communication dans un congrès
9ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2007, Ile d'Oléron, France. pp.27-30, 2007
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00176940
Contributeur : David Coudert <>
Soumis le : jeudi 4 octobre 2007 - 23:47:02
Dernière modification le : jeudi 11 janvier 2018 - 06:20:16
Document(s) archivé(s) le : lundi 24 septembre 2012 - 13:11:04

Fichier

09-algotel2007final-hanusse.pd...
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : inria-00176940, version 1

Collections

Citation

Philippe Duchon, Nicole Eggemann, Nicolas Hanusse. Non-Searchability of Random Scale-Free Graphs. 9ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2007, Ile d'Oléron, France. pp.27-30, 2007. 〈inria-00176940〉

Partager

Métriques

Consultations de la notice

229

Téléchargements de fichiers

116