A branch‐and‐price algorithm for the (k, c)‐coloring problem. Issue 4 (27th November 2014)

• Record Type: Journal Article
• Authors: Malaguti, Enrico; Méndez‐Díaz, Isabel; José Miranda‐Bront, Juan; Zabala, Paula
• Is Part Of: Networks. Volume 65:Issue 4(2015:Jul.)
• Page Start: 353
• Page End: 366
• Publication Date: 2014-11-27
• Subjects: Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21579
• Languages: English
• ISSNs: 0028-3045

Abstract

<abstract abstract-type="main"> <title> <x xml:space="preserve">Abstract</x> </title> <p>In this article, we study the (<italic>k, c</italic>)‐coloring problem, a generalization of the vertex coloring problem where we have to assign <italic>k</italic> colors to each vertex of an undirected graph, and two adjacent vertices can share at most <italic>c</italic> colors. We propose a new formulation for the (<italic>k, c</italic>)‐coloring problem and develop a Branch‐and‐Price algorithm. We tested the algorithm on instances having from 20 to 80 vertices and different combinations for <italic>k</italic> and <italic>c</italic>, and compare it with a recent algorithm proposed in the literature. Computational results show that the overall approach is effective and has very good performance on instances where the previous algorithm fails. © 2014 Wiley Periodicals, Inc. NETWORKS, 2014 Vol. 65(4), 353–366 2015</p> </abstract>