Rechercher

[CCP15] d -extensibles de stables dans les graphes bipartis

Conférence Nationale avec comité de lecture : 16ème congrès annuel de la ROADEF, February 2015, pp.1, Marseille, France,

Auteurs: G. Cotté , M.-C. Costa , C. Picouleau

motcle:
Résumé: Considérons un système dans lequel des composants peuvent tomber en panne. Pour que le bon fonctionnement ne soit pas affecté en cas de défaillance, on souhaite maintenir une partie aussi petite que possible du système pour qu’en cas de panne dans l’autre partie, le système puisse toujours fonctionner dans de bonnes conditions. Autrement dit, on veut sélectionner une partie aussi grande que possible du système qu’il ne sera pas nécessaire de maintenir à tout prix et ainsi protéger un minimum d’éléments sans perturber le bon fonctionnement du système. Nous représentons ici le système par un graphe biparti G = (B,R,E) dont les sommets sont les éléments du système. Ces éléments pourraient ne pas fonctionner si un de leurs voisins fonctionne. Ainsi, pour que le système fonctionne, les éléments doivent former un ensemble stable. Le système fonctionne donc de façon optimale lorsque les éléments forment un ensemble stable de cardinal maximal. Soit d un entier positif. Dans notre problème, nous souhaitons déterminer le plus grand sous-ensemble F de sommets de G tel que tout stable de F de cardinal égal à d peut être complété en un stable de cardinal maximal de G en n’utilisant que des sommets qui n’appartiennent pas à F. Soit un graphe G = (V,E). Un ensemble stable deG est un ensemble de sommets qui sont deux à deux non adjacents. On note α(G) le cardinal maximal d’un stable de G. Les sommets de G qui appartiennent à tous les stables maximum de G sont appelés sommets forcés. Les sommets de G qui appartiennent à certains stables maximum de G mais pas à tous sont appelés sommets libres. Les autres sommets, qui n’appartiennent à aucun stable maximum, sont appelés les sommets exclus. Soit F ⊂ V. Un stable S ⊂ F de G est dit extensible par rapport à F si il existe un stable maximum S∗ de G tel que S∗∩F=S. Soit un entier d tel que 1≤d < α(G). Un ensemble F⊂V est un d-extensible de G si tout stable S⊂F de cardinal |S|=d est extensible par rapport à F. Nous recherchons des ensembles d-extensibles F de cardinal maximal. Ce problème est analogue au problème d’extension de couplage présenté dans [2]. Nous considérons tout d’abord un graphe bipartiG= (B,R,E) dont tous les sommets sont libres. À l’aide de la caractérisation des stables maximaux dans les graphe bipartis présenté dans [1], nous caractérisons les stables extensibles ainsi que les ensembles d-extensibles. Nous prouvons ensuite que si d≥2, un d-extensible est aussi un k-extensible pour tout k > d. Nous donnons ensuite des exemples de graphes dans lesquels cette propriété n’est pas vérifiée pour d= 1. Nous proposons une borne inférieure de la cardinalité maximale d’un d-extensible. Dans le cas où G est un arbre dont tous les sommets sont libres, nous donnons une autre borne inférieure de la cardinalité maximale d’un d-extensible. Nous proposons ensuite un algorithme polynomial pour déterminer des d-extensibles optimaux dans une classe particulière d’arbres. Nous considérons ensuite un graphe biparti G= (B,R,E) dont tous les sommets sont libres ou forcés. Nous démontrons que pour certaines valeurs de d il existe un d-extensible optimal qui ne contient que des sommets libres et que pour d’autres valeurs de d, il est possible de déterminer un d-extensible optimal en temps polynomial. [1]C. Bentz, M.-C. Costa, C. Picouleau, B. Ries, D. de Werra d-transversals of Stable Sets and Vertex Covers in Weighted Bipartite Graphs, Journal of Discrete Algorithms 17 (2012), 95–102 [2]M. D. Plummer Recent Progress in Matching Extension, Royal Society, Mathematical Studies, 19, (2008), 427–457

BibTeX

@inproceedings {
CCP15,
title="{d -extensibles de stables dans les graphes bipartis}",
author=" G. Cotté and M.-C. Costa and C. Picouleau ",
booktitle="{16ème congrès annuel de la ROADEF}",
year=2015,
month="February",
pages="1",
address="Marseille, France",
}