Algorithme exact et approché pour le calcul de l'hyperbolicité d'un graphe

Creators: Cohen, Nathann; Coudert, David; Lancin, Aurélien

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).

Algorithme exact et approché pour le calcul de l'hyperbolicité d'un graphe

Description

Abstract

Abstract

Additional details