La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

A Minimal-State Processing Search Algorithm for Graph Coloring Problems Un algorithme de recherche de traitement à état minimal pour les problèmes de coloration de graphiques

Nobuo FUNABIKI, Teruo HIGASHINO

  • Vues en texte intégral

    0

  • Citer

Résumé:

Cet article présente un algorithme heuristique de coloration de graphes nommé MIPS_CLR, un algorithme de recherche de traitement à l'état MInimal pour le problème de graphe CoLoRing. Étant donné un graphique G(V, E), le but de ce problème NP-complet est de trouver une affectation de couleur à chaque sommet de V de sorte que toute paire de sommets adjacents ne doit pas recevoir la même couleur mais que le nombre total de couleurs doit également être minimisé. Le problème de la coloration des graphes a été largement étudié en raison de son grand nombre d’applications pratiques dans divers domaines. Dans MIPS_CLR, une étape de construction génère d'abord un état minimal initial composé d'autant de sommets colorés par un simple algorithme glouton, après une clique maximale de G est trouvé par un algorithme de clique maximale. Ensuite, une étape de raffinement recherche itérativement un état solution tout en gardant la minimalité en termes de fonction de coût par une méthode de transition à état minimal. Dans ce procédé, les schémas d'une meilleure sélection de couleurs, d'une sélection de couleurs aléatoire, d'un mélange d'attribution de couleurs et d'une expansion progressive des couleurs sont utilisés ensemble pour réaliser la recherche de descente discrète avec des capacités d'escalade. Les performances de MIPS_CLR sont évaluées en résolvant des instances de graphiques de référence DIMACS, où la qualité de la solution est généralement meilleure que celle des algorithmes existants tandis que le temps de calcul est comparable au meilleur existant. En particulier, MIPS_CLR fournit de nouvelles solutions de borne inférieure pour plusieurs instances. Les résultats de la simulation confirment la capacité de recherche étendue de notre approche MIPS_CLR pour le problème de coloration des graphes.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.7 pp.1420-1430
Date de publication
2000/07/25
Publicisé
ISSN en ligne
DOI
Type de manuscrit
PAPER
Catégories
Graphiques et réseaux

Auteurs

Mots-clés

Table des matières