Dans un réseau uni-directionnel,
l'établissement d'une communication de groupe se fait par la recherche
d'une sous-structure de cout minimum
qui sera utilisée pour cette communication. Dans le cas particulier
où le groupe comprend tous les noeuds du
réseau et où la communication entre
tout couple de noeuds du réseau est possible, on peut modéliser
la recherche de la structure minimale
par le problème suivant:
Problème MSSS (Minimum Strong Spanning Sub-digraph):
Instance : D un digraphe fortement connexe.
Question :
Trouver un sous-digraphe fortement connexe couvrant D et ayant un
nombre minimum d'arcs.
Le problème est NP-difficile, cependant des algorithmes polynomiaux
d'approximations sont connus, le meilleur à ce jour réalisant un
facteur 1.5 et étant dû à A. Vetta
Par ailleurs, une conjecture proposée en 1995 par J. A. Bondy, affirme
qu' il est possible de recouvrir tout digraphe D fortement
connexe et de stabilité alpha (D) par au plus alpha (D)
circuits, l'union de ces circuits ayant au plus |D|+
alpha (D)) -c
arcs, où D désigne le nombre de sommets de D, et
c le nombre de composantes connexes de cette union. Ceci étend une
question de T. Gallai affirmant que tout digraphe D fortement
connexe peut être couvert par alpha (D) circuits. Avec
S. Thomassé, nous prouvons cette dernière conjecture ainsi qu'un
corollaire de la conjecture de Bondy : tout digraphe D
fortement connexe de stabilité alpha (D) possède un
sous-digraphe fortement connexe couvrant ayant au plus |alpha
(D)|+2alpha (D) -2 arcs. Cette construction se fait en
temps polynomial, fournissant ainsi une $1+2alpha
(D)/|D|-approximation pour le problème
MSSS. L'algorithme présenté ici sera donc utile pour des digraphes
denses (alpha (D)<|D|/4).