An extraction and expansion approach for graph coloring. (English) Zbl 1278.90420
Summary: We present an extraction and expansion approach for the graph coloring problem. The extraction phase transforms a large graph into a sequence of progressively smaller graphs by removing large independent sets from the graph. The expansion phase starts by generating an approximate coloring for the smallest graph in the sequence. Then it expands the smallest graph by progressively adding back the extracted independent sets and determine a coloring for each intermediate graph. To color each graph, a simple perturbation based tabu search algorithm is used. The proposed approach is evaluated on the DIMACS challenge benchmarks showing competitive results in comparison with the state-of-the-art methods.
MSC:
| 90C35 | Programming involving graphs or networks |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C15 | Coloring of graphs and hypergraphs |
References:
| [1] | DOI: 10.1016/S0377-2217(02)00832-9 · Zbl 1053.90050 · doi:10.1016/S0377-2217(02)00832-9 |
| [2] | DOI: 10.1016/j.cor.2006.05.014 · Zbl 1278.90327 · doi:10.1016/j.cor.2006.05.014 |
| [3] | DOI: 10.1145/359094.359101 · Zbl 0394.05022 · doi:10.1145/359094.359101 |
| [4] | DOI: 10.1016/j.ejor.2005.08.012 · Zbl 1137.90602 · doi:10.1016/j.ejor.2005.08.012 |
| [5] | DOI: 10.1016/S0377-2217(87)80148-0 · Zbl 0626.90067 · doi:10.1016/S0377-2217(87)80148-0 |
| [6] | DOI: 10.1016/S0166-218X(99)00105-5 · Zbl 0946.68026 · doi:10.1016/S0166-218X(99)00105-5 |
| [7] | R. Dorne and J. K. Hao, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization (1998) pp. 77–92. |
| [8] | DOI: 10.1007/BFb0056916 · doi:10.1007/BFb0056916 |
| [9] | DOI: 10.1007/BF02125407 · Zbl 0851.90095 · doi:10.1007/BF02125407 |
| [10] | C. Fleurent and J. A. Ferland, Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Dimacs Series in Discrete Mathematics and Theoretical Computer Science 26, eds. D. S. Jhonson and M. Trick (1996) pp. 619–652. · doi:10.1090/dimacs/026/29 |
| [11] | Funabiki N., IEICE Transaction Fundamentals E 83 pp 1420– (2000) |
| [12] | DOI: 10.1023/A:1009823419804 · Zbl 0958.90071 · doi:10.1023/A:1009823419804 |
| [13] | DOI: 10.1016/j.cor.2005.07.028 · Zbl 1086.90060 · doi:10.1016/j.cor.2005.07.028 |
| [14] | DOI: 10.1016/j.dam.2006.07.017 · Zbl 1131.05089 · doi:10.1016/j.dam.2006.07.017 |
| [15] | DOI: 10.1109/TCS.1976.1084138 · Zbl 0342.94021 · doi:10.1109/TCS.1976.1084138 |
| [16] | Garey M. R., Computers and Intractability: A Guide to the Theory of NP-completeness (1979) · Zbl 0411.68039 |
| [17] | DOI: 10.1016/j.dam.2012.06.007 · Zbl 1251.05059 · doi:10.1016/j.dam.2012.06.007 |
| [18] | DOI: 10.1007/BF02239976 · Zbl 0626.68051 · doi:10.1007/BF02239976 |
| [19] | DOI: 10.1016/j.dam.2008.03.022 · Zbl 1213.05085 · doi:10.1016/j.dam.2008.03.022 |
| [20] | DOI: 10.1287/opre.39.3.378 · Zbl 0739.90055 · doi:10.1287/opre.39.3.378 |
| [21] | Johnson D. S., Dimacs Series in Discrete Mathematics and Theoretical Computer Science 26, in: Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge (1996) · Zbl 0875.68678 |
| [22] | DOI: 10.6028/jres.084.024 · Zbl 0437.68021 · doi:10.6028/jres.084.024 |
| [23] | DOI: 10.1016/j.ejor.2008.12.007 · Zbl 1190.90166 · doi:10.1016/j.ejor.2008.12.007 |
| [24] | DOI: 10.1287/ijoc.1070.0245 · Zbl 1243.90226 · doi:10.1287/ijoc.1070.0245 |
| [25] | C. Morgenstern, Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Dimacs Series in Discrete Mathematics and Theoretical Computer Science 26, eds. D. S. Johnson and M. Trick (American Mathematical Society, Boston, USA, 1996) pp. 335–357. |
| [26] | DOI: 10.1016/j.cor.2009.06.024 · Zbl 1176.90613 · doi:10.1016/j.cor.2009.06.024 |
| [27] | DOI: 10.1016/j.cor.2010.01.015 · Zbl 1188.90269 · doi:10.1016/j.cor.2010.01.015 |
| [28] | DOI: 10.1016/S0377-2217(98)80006-4 · Zbl 0943.90056 · doi:10.1016/S0377-2217(98)80006-4 |
| [29] | DOI: 10.1142/S021759590800181X · Zbl 1151.90531 · doi:10.1142/S021759590800181X |
| [30] | DOI: 10.1016/j.disopt.2010.12.001 · Zbl 1244.05097 · doi:10.1016/j.disopt.2010.12.001 |
| [31] | Wu Q., Journal of Combinatorial Optimization (2011) |
| [32] | DOI: 10.1016/j.cor.2011.04.002 · Zbl 1250.05007 · doi:10.1016/j.cor.2011.04.002 |
| [33] | DOI: 10.1007/s10878-008-9140-6 · Zbl 1198.05071 · doi:10.1007/s10878-008-9140-6 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
