Name
Abstract | ||
|---|---|---|
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. (c) 2014 Wiley Periodicals, Inc. NETWORKS, 2014 Vol. 65(4), 353-366 2015 |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1002/net.21579 | NETWORKS |
Keywords | Field | DocType |
vertex coloring,multicoloring,branch-and-price,computational experiments,column generation,heuristics,frequency assignment | Complete coloring,Combinatorics,Mathematical optimization,Vertex (geometry),Fractional coloring,Vertex (graph theory),Branch and price,Algorithm,Vertex cover,Greedy coloring,Mathematics,Feedback vertex set | Journal |
Volume | Issue | ISSN |
65.0 | SP4.0 | 0028-3045 |
Citations | PageRank | References |
2 | 0.38 | 15 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Enrico Malaguti | 1 | 312 | 21.69 |
| Isabel Méndez-Díaz | 2 | 268 | 18.73 |
| Juan José Miranda-Bront | 3 | 23 | 3.50 |
| Paula Zabala | 4 | 201 | 15.72 |