cohen:hal-00818441
Summary
Cohen, Nathann, Coudert, David and Lancin, Aurélien (2013) Algorithme exact et approché pour le calcul de l'hyperbolicité d'un graphe. In 15èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel). Pornic, France, May. (Nisse, Nicolas et Rousseau, Franck et Busnel, Yann, Eds.) Pages 1-4. ((URL)) (PDF)
Abstract
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).
Bibtex entry
@INPROCEEDINGS { cohen:hal-00818441,
HAL_ID = { hal-00818441 },
URL = { http://hal.archives-ouvertes.fr/hal-00818441 },
TITLE = { Algorithme exact et approché pour le calcul de l'hyperbolicité d'un graphe },
AUTHOR = { Cohen, Nathann and Coudert, David and Lancin, Aurélien },
ABSTRACT = { 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). },
KEYWORDS = { Hyperbolicité;algorithme;graphe;approximation },
LANGUAGE = { Fran{\c c}ais },
AFFILIATION = { Laboratoire de Recherche en Informatique - LRI , COATI - Inria Sophia Antipolis / Laboratoire I3S },
PAGES = { 1-4 },
ADDRESS = { Pornic, France },
BOOKTITLE = { 15èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel) },
EDITOR = { Nisse, Nicolas et Rousseau, Franck et Busnel, Yann },
NOTE = { Page 1-4 },
AUDIENCE = { internationale },
YEAR = { 2013 },
MONTH = { May },
PDF = { http://hal.archives-ouvertes.fr/hal-00818441/PDF/algotel2013-rev.pdf },
}