An Efficient Memetic Algorithm for the Minimum Load Coloring Problem

Zhiqiang Zhang, Zhongwen Li, Xiaobing Qiao and Weijun Wang
Additional contact information
Zhiqiang Zhang: Key Laboratory of Pattern Recognition and Intelligent Information Processing, Institutions of Higher Education of Sichuan Province, Chengdu University, Chengdu 610106, China
Zhongwen Li: Key Laboratory of Pattern Recognition and Intelligent Information Processing, Institutions of Higher Education of Sichuan Province, Chengdu University, Chengdu 610106, China
Xiaobing Qiao: College of Teachers, Chengdu University, Chengdu 610106, China
Weijun Wang: School of Information Science and Engineering, Chengdu University, Chengdu 610106, China

Mathematics, 2019, vol. 7, issue 5, 1-20

Abstract: Given a graph G with n vertices and l edges, the load distribution of a coloring q : V → {red, blue} is defined as d q = ( r q , b q ), in which r q is the number of edges with at least one end-vertex colored red and b q is the number of edges with at least one end-vertex colored blue. The minimum load coloring problem (MLCP) is to find a coloring q such that the maximum load, l q = 1/ l × max{ r q , b q }, is minimized. This problem has been proved to be NP-complete. This paper proposes a memetic algorithm for MLCP based on an improved K-OPT local search and an evolutionary operation. Furthermore, a data splitting operation is executed to expand the data amount of global search, and a disturbance operation is employed to improve the search ability of the algorithm. Experiments are carried out on the benchmark DIMACS to compare the searching results from memetic algorithm and the proposed algorithms. The experimental results show that a greater number of best results for the graphs can be found by the memetic algorithm, which can improve the best known results of MLCP.

Keywords: minimum load coloring; memetic algorithm; evolutionary; local search (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/7/5/475/pdf (application/pdf)
https://www.mdpi.com/2227-7390/7/5/475/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:7:y:2019:i:5:p:475-:d:234245

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().