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
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.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Nobuo FUNABIKI, Teruo HIGASHINO, "A Minimal-State Processing Search Algorithm for Graph Coloring Problems" in IEICE TRANSACTIONS on Fundamentals,
vol. E83-A, no. 7, pp. 1420-1430, July 2000, doi: .
Abstract: This paper presents a heuristic graph coloring algorithm named MIPS_CLR, a MInimal-state Processing Search algorithm for the graph CoLoRing problem. Given a graph G(V, E), the goal of this NP-complete problem is to find a color assignment to every vertex in V such that any pair of adjacent vertices must not receive the same color but also the total number of colors should be minimized. The graph coloring problem has been widely studied due to its large number of practical applications in various fields. In MIPS_CLR, a construction stage first generates an initial minimal state composed of as many as colored vertices by a simple greedy algorithm, after a maximal clique of G is found by a maximum clique algorithm. Then, a refinement stage iteratively seeks a solution state while keeping minimality in terms of a cost function by a minimal-state transition method. In this method, the schemes of a best color selection, a random color selection, a color assignment shuffle, and a gradual color expansion are used together to realize the discrete descent search with hill-climbing capabilities. The performance of MIPS_CLR is evaluated through solving DIMACS benchmark graph instances, where the solution quality is generally better than existing algorithms while the computation time is comparable with the best existing one. In particular, MIPS_CLR provides new lower bound solutions for several instances. The simulation results confirm the extensive search capability of our MIPS_CLR approach for the graph coloring problem.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_7_1420/_p
Copier
@ARTICLE{e83-a_7_1420,
author={Nobuo FUNABIKI, Teruo HIGASHINO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Minimal-State Processing Search Algorithm for Graph Coloring Problems},
year={2000},
volume={E83-A},
number={7},
pages={1420-1430},
abstract={This paper presents a heuristic graph coloring algorithm named MIPS_CLR, a MInimal-state Processing Search algorithm for the graph CoLoRing problem. Given a graph G(V, E), the goal of this NP-complete problem is to find a color assignment to every vertex in V such that any pair of adjacent vertices must not receive the same color but also the total number of colors should be minimized. The graph coloring problem has been widely studied due to its large number of practical applications in various fields. In MIPS_CLR, a construction stage first generates an initial minimal state composed of as many as colored vertices by a simple greedy algorithm, after a maximal clique of G is found by a maximum clique algorithm. Then, a refinement stage iteratively seeks a solution state while keeping minimality in terms of a cost function by a minimal-state transition method. In this method, the schemes of a best color selection, a random color selection, a color assignment shuffle, and a gradual color expansion are used together to realize the discrete descent search with hill-climbing capabilities. The performance of MIPS_CLR is evaluated through solving DIMACS benchmark graph instances, where the solution quality is generally better than existing algorithms while the computation time is comparable with the best existing one. In particular, MIPS_CLR provides new lower bound solutions for several instances. The simulation results confirm the extensive search capability of our MIPS_CLR approach for the graph coloring problem.},
keywords={},
doi={},
ISSN={},
month={July},}
Copier
TY - JOUR
TI - A Minimal-State Processing Search Algorithm for Graph Coloring Problems
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1420
EP - 1430
AU - Nobuo FUNABIKI
AU - Teruo HIGASHINO
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E83-A
IS - 7
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - July 2000
AB - This paper presents a heuristic graph coloring algorithm named MIPS_CLR, a MInimal-state Processing Search algorithm for the graph CoLoRing problem. Given a graph G(V, E), the goal of this NP-complete problem is to find a color assignment to every vertex in V such that any pair of adjacent vertices must not receive the same color but also the total number of colors should be minimized. The graph coloring problem has been widely studied due to its large number of practical applications in various fields. In MIPS_CLR, a construction stage first generates an initial minimal state composed of as many as colored vertices by a simple greedy algorithm, after a maximal clique of G is found by a maximum clique algorithm. Then, a refinement stage iteratively seeks a solution state while keeping minimality in terms of a cost function by a minimal-state transition method. In this method, the schemes of a best color selection, a random color selection, a color assignment shuffle, and a gradual color expansion are used together to realize the discrete descent search with hill-climbing capabilities. The performance of MIPS_CLR is evaluated through solving DIMACS benchmark graph instances, where the solution quality is generally better than existing algorithms while the computation time is comparable with the best existing one. In particular, MIPS_CLR provides new lower bound solutions for several instances. The simulation results confirm the extensive search capability of our MIPS_CLR approach for the graph coloring problem.
ER -