Arbres couvrants presque disjoints - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Conference Papers Year : 2015

Arbres couvrants presque disjoints

Abstract

Dans un réseau, la recherche de plusieurs arbres couvrants avec des propriétés intéressantes a amené à l'introduc-tion de plusieurs notions : les arbres couvrants arête-disjoints, les arbres indépendants enracinés en un sommet et les arbres complètement indépendants. Afin de généraliser ces notions, nous introduisons la notion d'arbres couvrants (i, j)-disjoints, où i et j sont respectivement le nombre maximum de noeuds internes et d'arêtes communs aux arbres couvrants. Nous montrons que déterminer s'il existe deux arbres couvrants (i, j)-disjoints dans un graphe G est un problème NP-complet pour i et j quelconques, et nous déterminons les valeurs minimales de i et j qui garantissent l'existence de deux arbres couvrants (i, j)-disjoints dans certaines grilles.
Fichier principal
Vignette du fichier
main.pdf (74.47 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01148458 , version 1 (04-05-2015)

Identifiers

  • HAL Id : hal-01148458 , version 1

Cite

Nicolas Gastineau, Benoit Darties, Olivier Togni. Arbres couvrants presque disjoints. ALGOTEL 2015 — 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Jun 2015, Beaune, France. ⟨hal-01148458⟩
111 View
399 Download

Share

Gmail Facebook X LinkedIn More