The Unconstrained Binary Quadratic Programming for the Sum Coloring Problem

Sidi Mohamed Douiri and Souad Elbernoussi

Modern Applied Science, 2012, vol. 6, issue 9, 26

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.

Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://ccsenet.org/journal/index.php/mas/article/download/18489/13209 (application/pdf)
https://ccsenet.org/journal/index.php/mas/article/view/18489 (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:ibn:masjnl:v:6:y:2012:i:9:p:26

Access Statistics for this article

More articles in Modern Applied Science from Canadian Center of Science and Education Contact information at EDIRC.
Bibliographic data for series maintained by Canadian Center of Science and Education ().