Treewidth and Hyperbolicity of the Internet

Abstract : We study the measurement of the Internet according to two graph parameters: treewidth and hyperbolicity. Both tell how far from a tree a graph is. They are computed from snapshots of the Internet released by CAIDA, DIMES, AQUALAB, UCLA, Rocketfuel and Strasbourg University, at the AS or at the router level. On the one hand, the treewidth of the Internet appears to be quite large and being far from a tree with that respect, reflecting some high degree of connectivity. This proves the existence of a well linked core in the Internet. On the other hand, the hyperbolicity (as a graph parameter) appears to be very low, reflecting a tree-like structure with respect to distances. Additionally, we compute the treewidth and hyperbolicity obtained for classical Internet models and compare with the snapshots.
Type de document :
Communication dans un congrès
10th IEEE International Symposium on Network Computing and Applications (IEEE NCA), Aug 2011, Boston, United States. pp.25-32, 2011
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00909736
Contributeur : Laurent Viennot <>
Soumis le : mardi 26 novembre 2013 - 17:27:08
Dernière modification le : vendredi 31 août 2018 - 09:12:06
Document(s) archivé(s) le : jeudi 27 février 2014 - 10:56:11

Fichier

nca2011treeness.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00909736, version 1

Collections

Citation

Fabien De Montgolfier, Mauricio Soto, Laurent Viennot. Treewidth and Hyperbolicity of the Internet. 10th IEEE International Symposium on Network Computing and Applications (IEEE NCA), Aug 2011, Boston, United States. pp.25-32, 2011. 〈hal-00909736〉

Partager

Métriques

Consultations de la notice

294

Téléchargements de fichiers

192