Algorithme de recherche d'un stable de cardinalite maximum dans un graphe sans etoile

AbstractUn graphe est dit sans étoile si aucun de ses sommets n'est adjacent à trois sommets formant un stable. Les graphes adjoints sont des graphes sans étoile. Le problème de la recherche d'un stable de cardinalité maximum dans un graphe sans étoile peut donc être considéré comme une généralisation de celui du couplage maximum. L'algorithme présenté est une extension de l'algorithme du couplage d'Edmonds. Une chaîne augmentante par rapport à un stable maximal S d'un graphe sans étoile G=(X, E) est un sous-graphe de G qui est une chaîne dont les sommets appartiennent alternativement à S et à (X−S) et dont les extrêmités sont insaturées par S (i.e. adjacentes à un seul sommet de S). S est de cardinalité maximum si et seulement s'il n'existe pas de chaîne augmentante par rapport à S. Pour détecter une telle chaîne, nous utilisons une procédure de marquage des sommets qui nécessite deux opérations de réduction; l'une d'entre elles, analogue à celle des “blossom” d'Edmonds, réduit le graphe par rapport à un cycle impair sans corde, l'autre réduit le graphe par rapport à une clique. Cette procédure est différente de celle de Minty laquelle commence par chercher s'il existe des chaînes augmentantes de longueur trois ou cinq et ce par énumération, et ensuite à construire pour chaque couple de sommets insaturés non voisins, un graphe annexe et à y appliquer l'algorithme du couplage d'Edmonds afin de détecter l'existence d'une chaîne augmentante joignant les deux sommets insaturés choisis [6]