Expliquer l'algorithme 0-extension

Question

J'essaye d'implémenter l'algorithme 0-extension.

Il est utilisé pour colorer un graphique avec un nombre de couleurs où certains nœuds ont déjà une couleur assignée et où chaque bord a une distance. L'algorithme calcule une attribution de couleurs afin que les nœuds voisins de la même couleur aient la plus grande distance possible entre eux.

J'ai trouvé cet article expliquant l'algorithme: http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=1FBA2D22588CABDAA8ECF73B41BD3D72?doi=10.1.1.100.8049&rep=rep1&type=pdf mais je ne vois pas comment j'ai besoin de l'implémenter.

je l'ai déjà posé cette question sur le site « science informatique théorique », mais à mi-chemin de la discussion, nous sommes allés au-delà de la portée du site: https://cstheory.stackexchange.com/questions/6163/explain-0-extension-algorithm

Quelqu'un peut-il expliquer cet algorithme en termes simples? Je prévois de créer le code final opensource dans le paquetage jgrapht.

Answer 1

L'objectif de 0 extension est de minimiser le coût total pondéré des arêtes avec différents points d'extrémité de couleur plutôt que de maximiser, donc 0-extension est vraiment un problème de regroupement plutôt que d'un problème de coloration. Je suis généralement sceptique que l'utilisation d'un algorithme de clustering à la couleur aurait de bons résultats. Si vous voulez quelque chose avec une garantie théorique, vous pouvez vous pencher sur des approximations du problème MAXCUT (vraiment une généralisation s'il y a plus de deux couleurs), mais je soupçonne qu'un algorithme de recherche locale fonctionnerait mieux en pratique.