The search functionality is under construction.

The search functionality is under construction.

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.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.7 pp.1420-1430

- Publication Date
- 2000/07/25

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- PAPER

- Category
- Graphs and Networks

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.

Copy

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

Copy

@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},}

Copy

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 -