Skip to Main content Skip to Navigation
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.
Complete list of metadatas

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/inria-00176940
Contributor : David Coudert <>
Submitted on : Thursday, October 4, 2007 - 11:47:02 PM
Last modification on : Thursday, December 26, 2019 - 10:48:02 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

Identifiers

  • 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. ⟨inria-00176940⟩

Share

Metrics

Record views

254

Files downloads

367