Name
Title | ||
|---|---|---|
A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives. |
Abstract | ||
|---|---|---|
An equitable k-coloring of a graph is defined by a partition of its vertices into k disjoint stable subsets, such that the difference between the cardinalities of any two subsets is at most one. The equitable coloring problem consists of finding the minimum value of k such that a given graph can be equitably k-colored. We present two new integer programming formulations based on representatives for the equitable coloring problem. We propose a primal constructive heuristic, branching strategies, and the first branch-and-cut algorithm in the literature of the equitable coloring problem. The computational experiments were carried out on randomly generated graphs, DIMACS graphs, and other graphs from the literature. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.dam.2011.10.008 | Discrete Applied Mathematics |
Keywords | Field | DocType |
equitable k-coloring,k disjoint stable subsets,new integer programming formulation,computational experiment,branch-and-cut algorithm,minimum value,dimacs graph,primal constructive heuristic,equitable coloring problem,branch and cut | Discrete mathematics,Edge coloring,Complete coloring,Combinatorics,Fractional coloring,List coloring,Branch and cut,Algorithm,Greedy coloring,Mathematics,Equitable coloring,Graph coloring | Journal |
Volume | ISSN | Citations |
164 | 0166-218X | 8 |
PageRank | References | Authors |
0.54 | 15 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Laura Bahiense | 1 | 78 | 9.61 |
| Yuri Frota | 2 | 105 | 13.98 |
| Thiago F. Noronha | 3 | 197 | 16.95 |
| Celso C. Ribeiro | 4 | 1436 | 99.97 |