91社区

Probl猫mes de couverture dans les graphes : les codes identifiants et leurs relaxations continues.

Les codes identifiants ont 茅t茅 introduits par Karpovsky, Chakrabarty et Levitin en 1998 pour mod茅liser un probl猫me de d茅tection de d茅faillance dans des r茅seaux multiprocesseurs. Un code identifiant est un ensemble dominant de sommets tel que le voisinage ferm茅 de chaque sommet intersect茅 avec l'ensemble est unique. Le probl猫me de trouver un code identifiant a largement 茅t茅 茅tudi茅. Cependant, sa formulation en termes de programmation lin茅aire en nombres entier a rarement 茅t茅 consid茅r茅e. Dans cet expos茅, nous comparerons le probl猫me en nombres entiers avec sa relaxation continue et nous nous concentrerons sur le cas particulier des graphes sommets-transitifs.

听