|
 
|
[CCP17] d-extensibles de stables dans les graphes bipartis
Conférence Nationale avec comité de lecture : ROADEF, February 2017, pp.2 p., Metz, France,Mots clés: Ensembles stables, extenseurs, graphes, arbres, grilles.
Résumé:
Considérons un système dans lequel des composants peuvent tomber en panne. Il est possible
de maintenir des éléments pour éviter les pannes mais cela a un coût. 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 opérer dans de bonnes conditions.
Supposons que le système puisse être modélisé par un graphe G = (V,E) dans lequel les
sommets sont les composants et tel que le système ne fonctionne que si ces sommets forment
un ensemble stable. Le système fonctionne tant qu’il existe un stable de cardinal maximal
alpha(G). Soit d un entier tel que 0 <= d <= alpha(G). On souhaite déterminer le plus grand ensemble de sommets F tel que tout stable de cardinal d de G[F] peut être complété en un stable optimal
de G à l’aide de sommets de V − F.
Nous proposons une caractérisation des stables extensibles et des d-extensibles dans les
graphes bipartis, ainsi que des bornes inférieures du cardinal maximal d’un d-extensible dans
le cas d’un graphe biparti quelconque et dans le cas d’un arbre. Des cas particuliers sont
résolus, les grilles, les cycles et certaines classes d’arbres, graphes bipartis dont le
graphe des composantes est un arbre...
BibTeX
| @inproceedings { | |||
| CCP17, | |||
| title | = | "{d-extensibles de stables dans les graphes bipartis}", | |
| author | = | " G. Cotté and M.-C. Costa and C. Picouleau ", | |
| booktitle | = | "{ROADEF}", | |
| year | = | 2017, | |
| month | = | "February", | |
| pages | = | "2 p.", | |
| address | = | "Metz, France", | |
| } | |||
