Published May 28, 2013
| Version v1
Conference paper
Algorithme exact et approché pour le calcul de l'hyperbolicité d'un graphe
Creators
Contributors
Others:
- Laboratoire de Recherche en Informatique (LRI) ; Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)
- Combinatorics, Optimization and Algorithms for Telecommunications (COATI) ; Inria Sophia Antipolis - Méditerranée (CRISAM) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED) ; Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
- Nisse
- Nicolas and Rousseau
- Franck and Busnel
- Yann
- European Project: 258307,EC:FP7:ICT,FP7-ICT-2009-5,EULER(2010)
Description
Nous proposons un algorithme simple et efficace pour calculer l'hyperbolicité de grands graphes dont la complexité temporelle est fonction de la distribution des plus courts chemins dans les composantes biconnexes du graphe et de la valeur de l'hyperbolicité. Nous montrons également comment réduire la taille de l'instance en utilisant une décomposition par des cliques-séparatrices. L'algorithme peut de plus être utilisé pour fournir une approximation de l'hyperbolicité à un facteur multiplicatif ou une constante additive donnés. Nous évaluons les performances de notre algorithme sur des cartes des systèmes autonomes de l'Internet (CAIDA et DIMES).
Abstract
Page 1-4Abstract
International audienceAdditional details
Identifiers
- URL
- https://hal.archives-ouvertes.fr/hal-00818441
- URN
- urn:oai:HAL:hal-00818441v1
Origin repository
- Origin repository
- UNICA