Accueil🇫🇷Chercher

Algorithme de Wigderson

L'algorithme de Wigderson est un algorithme de coloration de graphe. C'est un algorithme de complexité en temps polynomiale, qui colore avec couleurs les graphes 3-coloriables. Il est dû à Avi Wigderson.

Description

Cet algorithme s'effectue sur des graphes qu'on sait 3-coloriables. Soit un tel graphe. On note le nombre de sommets de

  1. On prend comme couleur initiale
  2. Pour tout non déjà colorié et avec au moins voisins non coloriés : on considère le sous graphe induit par l'ensemble des voisins de pas encore coloriés, et on le 2-colorie avec les couleurs et On ajoute à le nombre de couleurs utilisées.
  3. Avec l'algorithme glouton, on colorie le reste des sommets avec des couleurs plus grandes que

La complexité de l'algorithme de Wigderson est polynomiale en et détermine un coloriage de qui utilise couleurs.

Correction de l'algorithme de Wigderson

L'algorithme de Wigderson renvoie bien un coloriage, car l'algorithme glouton et l'algorithme de 2-coloriage sont corrects, et que les sous-graphes considérés dans l'algorithme sont coloriés avec des ensembles de couleur disjoints.

Si on note le nombre de sommets traités durant le point 2, alors l'algorithme colorie au moins sommets. On a donc :

, i.e .

Ainsi le nombre de couleurs utilisées dans le point 2 est d'au plus . Ensuite, le degré du sous-graphe induit par les sommets non coloriés à la fin du point 2 est inférieur ou égal à . L'algorithme glouton utilise donc au plus couleurs pour colorier le reste des sommets. Ainsi, le nombre de couleurs utilisées est d'au plus , il est donc en .

Exemple

Le graphe suivant est 3-coloriable :

Graphe 3-coloriable

Application de l'étape 2

Le sommet a 4 voisins non coloriés : on les 2-colorie, puis on fait de même pour les 4 voisins non coloriés du sommet .

Après ces opérations, il n'y a plus de sommet non colorié avec au moins voisins non coloriés.

Étape 2 de l'algorithme de Wigderson

Application de l'étape 3

On applique l'algorithme glouton aux sommets restants.

Étape 3 de l'algorithme de Wigderson

Histoire

L'algorithme a été publié en 1983 par Avi Wigderson[1].

Notes et références

  1. Avi Wigderson, « Improving the Performance Guarantee for Approximate Graph Coloring », Journal of the ACM, vol. 30, no 4,‎ , p. 729-735 (DOI 10.1145/2157.2158)
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.