The Unconstrained Binary Quadratic Programming for the Sum Coloring Problem

Sidi Mohamed Douiri, Souad Elbernoussi

Abstract


Several recent studies have shown the efficacy of unconstrained binary quadratic programming (UBQP) to model and solve many combinatorial problems. In this paper we are interested in the minimum sum coloring problem (MSCP), a new variant of the traditional graph coloring problem (GCP). We give a reformulation of the problem (MSCP) as an unconstrained binary quadratic binary programming, and we resolve it afterward by a genetic algorithms. The proposed algorithm is evaluated on the DIMACS challenge benchmarks and computational results show that the proposed UBQP model achieves highly competitive results, compared with 4 state-of-the-art algorithms.


Full Text: PDF DOI: 10.5539/mas.v6n9p26

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

Modern Applied Science   ISSN 1913-1844 (Print)   ISSN 1913-1852 (Online)

Copyright © Canadian Center of Science and Education

To make sure that you can receive messages from us, please add the 'ccsenet.org' domain to your e-mail 'safe list'. If you do not receive e-mail in your 'inbox', check your 'bulk mail' or 'junk mail' folders.