A Minimal-State Processing Search Algorthm for Graph Coloring Problems

• FUNABIKI Nobuo

  the Department of Informatics and Mathematical Science, Graduate School of Engineering Science, Osaka University

• HIGASHINO Teruo

  the Department of Informatics and Mathematical Science, Graduate School of Engineering Science, Osaka University

抄録

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 intial minimal state composed of as many as colored vertices by a simple greedy algorithm, after a miximal 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.

収録刊行物

• IEICE transactions on fundamentals of electronics, communications and computer sciences

  IEICE transactions on fundamentals of electronics, communications and computer sciences 83 (7), 1420-1430, 2000-07-25

  一般社団法人電子情報通信学会

キーワード

• graph coloring
• simulation
• heuristic algorithm
• MIPS_CLR
• DIMACS

詳細情報

• CRID: 1570572702403256448
• NII論文ID: 110003208670
• NII書誌ID: AA10826239
• ISSN: 09168508
• 本文言語コード: en
• データソース種別:
  • CiNii Articles