Diameter of Minimal Separators in Graphs

David Coudert 1 Guillaume Ducoffe 1 Nicolas Nisse 1
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é : Nous \'etablissons des relations g\'en\'erales entre les propri\'et\'es topologiques des graphes et leurs propri\'et\'es m\'etriques.Dans ce but, nous bornons sup\'erieurement le diam\`etre des \emph{s\'eparateurs minimaux} dans un graphe par une fonction de leur taille.Plus pr\'ecis\'ement, nous prouvons que, dans n'importe quel graphe $G$, le diam\`etre de tout s\'eparateur minimal $S$ dans $G$ est au plus $\lfloor \frac{\ell(G)} {2}\rfloor \cdot (|S|-1)$ avec $\ell(G)$ la plus grande taille d'un cycle isom\'etrique dans $G$.Nous am\'eliorons cette borne dans le cas des graphes pour lesquels il existe un \emph{ordre d'\'elimination isom\'etrique}: nous prouvons que tout s\'eparareur minimal $S$ dans un tel graphe a pour diam\`etre au plus $2 (|S|-1)$. Nos preuves sont principalement bas\'ees sur le fait que les s\'eparateurs minimaux dans un graphe $G$ sont connexes dans l'une de ses puissances.Une cons\'equence facile de nos r\'esultats est que pour tout graphe $G$, la \emph{treelength} $tl(G)$ est au plus $\lfloor \frac{\ell(G)} {2}\rfloor$ fois sa \emph{treewidth} $tw(G)$.En compl\'ement de cette relation, nous prouvons que, pour tout graphe $G$ qui exclut un \emph{apex graph} $H$ comme mineur, $tw(G) \leq c_H \cdot tl(G)$ avec $c_H$ une constante qui ne d\'epend que de $H$.Nous am\'eliorons cette constante dans le cas o\`u $G$ est de genre born\'e.En cons\'equence de quoi, nous obtenons un algorithme tr\`es simple avec facteur d'approximation $O(\ell(G))$ pour calculer la treewidth des graphes qui excluent un apex graph comme mineur en temps $O(n m)$.
Type de document :
Rapport
[Research Report] RR-8639, Inria Sophia Antipolis; I3S; INRIA. 2014, pp.16
Liste complète des métadonnées

https://hal.inria.fr/hal-01088423
Contributeur : Nicolas Nisse <>
Soumis le : vendredi 19 décembre 2014 - 13:36:16
Dernière modification le : mercredi 14 décembre 2016 - 01:07:06

Fichier

RR-8639_dec2014.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01088423, version 2

Collections

Citation

David Coudert, Guillaume Ducoffe, Nicolas Nisse. Diameter of Minimal Separators in Graphs. [Research Report] RR-8639, Inria Sophia Antipolis; I3S; INRIA. 2014, pp.16. <hal-01088423v2>

Partager

Métriques

Consultations de
la notice

263

Téléchargements du document

198