Premium
A branch‐and‐price algorithm for the ( k,c )‐coloring problem
Author(s) -
Malaguti Enrico,
MéndezDíaz Isabel,
José MirandaBront Juan,
Zabala Paula
Publication year - 2015
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21579
Subject(s) - fractional coloring , complete coloring , list coloring , combinatorics , vertex (graph theory) , greedy coloring , undirected graph , generalization , graph coloring , algorithm , mathematics , computer science , graph , graph power , mathematical analysis , line graph
In this article, we study the ( k,c )‐coloring problem, a generalization of the vertex coloring problem where we have to assign k colors to each vertex of an undirected graph, and two adjacent vertices can share at most c colors. We propose a new formulation for the ( k,c )‐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 k and c , 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