6533b836fe1ef96bd12a1107

RESEARCH PRODUCT

Arbres couvrants presque disjoints

Nicolas Gastineau Benoit Darties Olivier Togni

subject

[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM][INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI]Arbres couvrantsArbres couvrants com-plètement indépendants[INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI][ INFO.INFO-NI ] Computer Science [cs]/Networking and Internet Architecture [cs.NI]Ensembles dominants connexes[ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM][INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]Arbres couvrants arête-disjointsArbres couvrants indépendants

description

International audience; 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.

yearjournalcountryeditionlanguage
2015-06-02
https://hal.archives-ouvertes.fr/hal-01148458/document