A branch‐and‐price algorithm for the (k,c)‐coloring problem
Copyright policy )A branch‐and‐price algorithm for the (k,c)‐coloring problem
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
Vertex Coloring, column generation, vertex coloring; multicoloring; branch-and-price; computational experiments; column generation; heuristics; frequency assignment, Column Generation, Branch-And-Price, heuristics, Computational Experiments, Coloring of graphs and hypergraphs, computational experiments, vertex coloring, branch-and-price, Graph algorithms (graph-theoretic aspects), frequency assignment, Heuristics, Frequency Assignment, https://purl.org/becyt/ford/1.2, https://purl.org/becyt/ford/1, multicoloring, Multicoloring
Vertex Coloring, column generation, vertex coloring; multicoloring; branch-and-price; computational experiments; column generation; heuristics; frequency assignment, Column Generation, Branch-And-Price, heuristics, Computational Experiments, Coloring of graphs and hypergraphs, computational experiments, vertex coloring, branch-and-price, Graph algorithms (graph-theoretic aspects), frequency assignment, Heuristics, Frequency Assignment, https://purl.org/becyt/ford/1.2, https://purl.org/becyt/ford/1, multicoloring, Multicoloring
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).3 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!