{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T09:38:14Z","timestamp":1725615494966},"reference-count":33,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Asia Pac. J. Oper. Res."],"published-print":{"date-parts":[[2013,10]]},"abstract":"This paper presents 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.<\/jats:p>","DOI":"10.1142\/s0217595913500188","type":"journal-article","created":{"date-parts":[[2013,10,3]],"date-time":"2013-10-03T03:35:41Z","timestamp":1380771341000},"page":"1350018","source":"Crossref","is-referenced-by-count":11,"title":["AN EXTRACTION AND EXPANSION APPROACH FOR GRAPH COLORING"],"prefix":"10.1142","volume":"30","author":[{"given":"QINGHUA","family":"WU","sequence":"first","affiliation":[{"name":"School of Management, Huazhong University of Science and Technology, No. 1037, Luoyu Road, Wuhan, China"},{"name":"LERIA, Universit\u00e9, Universit\u00e9 d'Angers, 2 Boulevard Lavoisier, 49045 Angers Cedex 01, France"}]},{"given":"JIN-KAO","family":"HAO","sequence":"additional","affiliation":[{"name":"LERIA, Universit\u00e9, Universit\u00e9 d'Angers, 2 Boulevard Lavoisier, 49045 Angers Cedex 01, France"}]}],"member":"219","published-online":{"date-parts":[[2013,10,2]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(02)00832-9"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2006.05.014"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1145\/359094.359101"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2005.08.012"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(87)80148-0"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00105-5"},{"key":"rf8","unstructured":"R.\u00a0Dorne and J. K.\u00a0Hao, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization (1998)\u00a0pp. 77\u201392."},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0056916"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02125407"},{"key":"rf11","unstructured":"C.\u00a0Fleurent and J. A.\u00a0Ferland, Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Dimacs Series in Discrete Mathematics and Theoretical Computer Science\u00a026, eds. D. S.\u00a0Jhonson and M.\u00a0Trick (1996)\u00a0pp. 619\u2013652."},{"key":"rf12","first-page":"1420","volume":"83","author":"Funabiki N.","year":"2000","journal-title":"IEICE Transaction Fundamentals E"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009823419804"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2005.07.028"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.07.017"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1109\/TCS.1976.1084138"},{"key":"rf17","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"Garey M. R.","year":"1979"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.06.007"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02239976"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.03.022"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1287\/opre.39.3.378"},{"key":"rf23","series-title":"Dimacs Series in Discrete Mathematics and Theoretical Computer Science","doi-asserted-by":"crossref","DOI":"10.1090\/dimacs\/026\/01","volume-title":"Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge","volume":"26","author":"Johnson D. S.","year":"1996"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.6028\/jres.084.024"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2008.12.007"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1070.0245"},{"key":"rf27","doi-asserted-by":"crossref","unstructured":"C.\u00a0Morgenstern, Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Dimacs Series in Discrete Mathematics and Theoretical Computer Science\u00a026, eds. D. S.\u00a0Johnson and M.\u00a0Trick (American Mathematical Society, Boston, USA, 1996)\u00a0pp. 335\u2013357.","DOI":"10.1090\/dimacs\/026\/16"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2009.06.024"},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2010.01.015"},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(98)80006-4"},{"key":"rf31","doi-asserted-by":"publisher","DOI":"10.1142\/S021759590800181X"},{"key":"rf32","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.12.001"},{"key":"rf33","author":"Wu Q.","year":"2011","journal-title":"Journal of Combinatorial Optimization"},{"key":"rf34","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2011.04.002"},{"key":"rf35","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-008-9140-6"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0217595913500188","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,7]],"date-time":"2022-03-07T19:56:26Z","timestamp":1646682986000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0217595913500188"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10]]},"references-count":33,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2013,10,2]]},"published-print":{"date-parts":[[2013,10]]}},"alternative-id":["10.1142\/S0217595913500188"],"URL":"https:\/\/doi.org\/10.1142\/s0217595913500188","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"value":"0217-5959","type":"print"},{"value":"1793-7019","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,10]]}}}