Structure vs métrique dans les graphesReport as inadecuate




Structure vs métrique dans les graphes - Download this document for free, or read online. Document in PDF available to download.

1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués

Résumé : L-émergence de réseaux de très grande taille oblige à repenser de nombreux problèmes sur les graphes : en apparence simples, mais pour lesquels les algorithmes de résolution connus ne passent plus a l-échelle. Une approche possible est de mieux comprendre les propriétés de ces réseaux complexes, et d-en déduire de nouvelles méthodes plus efficaces. C-est dans ce but que nous démontrons des relations générales entre les propriétés structurelles des graphes et leurs propriétés métriques. Nos relations se déduisent de nouvelles bornes serrées sur le diamètre des séparateurs minimaux dans un graphe. Plus précisément , nous prouvons que dans tout graphe G le diamètre d-un séparateur minimal S dans G est au plus lG-2 · |S| − 1, avec lG la plus grande taille d-un cycle isométrique dans G. Nos preuves reposent sur des propriétés de connexité dans les puissances d-un graphe. Une conséquence de nos résultats est que pour tout graphe G, sa longueur arborescente treelength est au plus lG-2 fois sa largeur arborescente treewidth. En complément de cette relation, nous bornons la largeur arborescente par une fonction de la longueur arborescente et du genre du graphe. Cette borne se généralise à la famille des graphes qui excluent un apex-graph H comme mineur. Par conséquent , nous obtenons un algorithme très simple qui, étant donné un graphe excluant un apex-graph fixé comme mineur, calcule sa largeur arborescente en temps On² et avec facteur d-approximation OlG.

Mots-clés : Genre Hyperbolicité Graphe Largeur arborescente Treewidth Longueur arborescente Treelength





Author: David Coudert - Guillaume Ducoffe - Nicolas Nisse -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents