Reduction and Local Search for Weighted Graph Coloring Problem

Authors

  • Yiyuan Wang Northeast Normal University
  • Shaowei Cai Chinese Academy of Sciences
  • Shiwei Pan Northeast Normal University
  • Ximing Li Jilin University
  • Monghao Yin Northeast Normal University

DOI:

https://doi.org/10.1609/aaai.v34i03.5624

Abstract

The weighted graph coloring problem (WGCP) is an important extension of the graph coloring problem (GCP) with wide applications. Compared to GCP, where numerous methods have been developed and even massive graphs with millions of vertices can be solved well, fewer works have been done for WGCP, and no solution is available for solving WGCP for massive graphs. This paper explores techniques for solving WGCP, including a lower bound and a reduction rule based on clique sampling, and a local search algorithm based on two selection rules and a new variant of configuration checking. This results in our algorithm RedLS (Reduction plus Local Search). Experiments are conducted to compare RedLS with the state-of-the-art algorithms on massive graphs as well as conventional benchmarks studied in previous works. RedLS exhibits very good performance and robustness. It significantly outperforms previous algorithms on all benchmarks.

Downloads

Published

2020-04-03

How to Cite

Wang, Y., Cai, S., Pan, S., Li, X., & Yin, M. (2020). Reduction and Local Search for Weighted Graph Coloring Problem. Proceedings of the AAAI Conference on Artificial Intelligence, 34(03), 2433-2441. https://doi.org/10.1609/aaai.v34i03.5624

Issue

Section

AAAI Technical Track: Heuristic Search and Optimization