{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T20:48:37Z","timestamp":1761598117184},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T00:00:00Z","timestamp":1568764800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T00:00:00Z","timestamp":1568764800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Wireless Pers Commun"],"published-print":{"date-parts":[[2020,2]]},"DOI":"10.1007\/s11277-019-06778-0","type":"journal-article","created":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T14:06:07Z","timestamp":1568815567000},"page":"1143-1155","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["A Tree Based Novel Approach for Graph Coloring Problem Using Maximal Independent Set"],"prefix":"10.1007","volume":"110","author":[{"given":"Prakash C.","family":"Sharma","sequence":"first","affiliation":[]},{"given":"Narendra S.","family":"Chaudhari","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,9,18]]},"reference":[{"key":"6778_CR1","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. San Francisco: W.H. Freeman and Company."},{"issue":"2\u20133","key":"6778_CR2","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/S0166-218X(99)00105-5","volume":"93","author":"D de Werra","year":"1999","unstructured":"de Werra, D., Eisenbeis, C., Lelait, S., & Marmol, B. (1999). On a graph-theoretical model for cyclic register allocation. Discrete Applied Mathematics,93(2\u20133), 191\u2013203.","journal-title":"Discrete Applied Mathematics"},{"key":"6778_CR3","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/j.ejor.2005.08.012","volume":"176","author":"EK Burke","year":"2007","unstructured":"Burke, E. K., McCollum, B., Meisels, A., Petrovic, S., & Qu, R. (2007). A graph-based hyper heuristic for timetabling problems. European Journal of Operational Research,176, 177\u2013192.","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"6778_CR4","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/S0377-2217(98)80006-4","volume":"107","author":"DH Smith","year":"1998","unstructured":"Smith, D. H., Hurley, S., & Thiel, S. U. (1998). Improving heuristics for the frequency assignment problem. European Journal of Operational Research,107(1), 76\u201386.","journal-title":"European Journal of Operational Research"},{"issue":"4","key":"6778_CR5","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s10951-008-0066-8","volume":"11","author":"N Zufferey","year":"2008","unstructured":"Zufferey, N., Amstutz, P., & Giaccari, P. (2008). Graph colouring approaches for a satellite range scheduling problem. Journal of Scheduling,11(4), 263\u2013277.","journal-title":"Journal of Scheduling"},{"key":"6778_CR6","first-page":"85","volume-title":"Reducibility among combinatorial problems","author":"RM Karp","year":"1972","unstructured":"Karp, R. M. (1972). Reducibility among combinatorial problems (pp. 85\u2013103). New York: Plenum Press."},{"issue":"4","key":"6778_CR7","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1145\/359094.359101","volume":"22","author":"D Brelez","year":"1979","unstructured":"Brelez, D. (1979). New methods to color the vertices of a graph. Communications of the ACM,22(4), 251\u2013256.","journal-title":"Communications of the ACM"},{"issue":"6","key":"6778_CR8","doi-asserted-by":"publisher","first-page":"489","DOI":"10.6028\/jres.084.024","volume":"84","author":"FT Leighton","year":"1979","unstructured":"Leighton, F. T. (1979). A graph coloring algorithm for large scheduling problems. Journal of Research of the National Bureau of Standards,84(6), 489\u2013506.","journal-title":"Journal of Research of the National Bureau of Standards"},{"issue":"3","key":"6778_CR9","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1016\/j.cor.2006.05.014","volume":"35","author":"I Blochligerand","year":"2008","unstructured":"Blochligerand, I., & Zufferey, N. (2008). A graph coloring heuristic using partial solutions and a reactive tabu scheme. Computers & Operations Research,35(3), 960\u2013975.","journal-title":"Computers & Operations Research"},{"key":"6778_CR10","first-page":"77","volume-title":"Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization","author":"R Dorne","year":"1998","unstructured":"Dorne, R., & Hao, J. K. (1998). Tabu search for graph coloring, T-colorings and set T-colorings. In S. Vo\u00df, S. Martello, I. H. Osman, & C. Roucairol (Eds.), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization (pp. 77\u201392). New York: Springer."},{"key":"6778_CR11","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/BF02239976","volume":"39","author":"A Hertz","year":"1987","unstructured":"Hertz, A., & de Werra, D. (1987). Using tabu search techniques for graph coloring. Computing,39, 345\u2013351.","journal-title":"Computing"},{"issue":"10","key":"6778_CR12","doi-asserted-by":"publisher","first-page":"1822","DOI":"10.1016\/j.cor.2010.01.015","volume":"37","author":"DC Porumbel","year":"2010","unstructured":"Porumbel, D. C., Hao, J. K., & Kuntz, P. (2010). An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring. Computers & Operations Research,37(10), 1822\u20131832.","journal-title":"Computers & Operations Research"},{"key":"6778_CR13","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/S0377-2217(87)80148-0","volume":"32","author":"M Chams","year":"1987","unstructured":"Chams, M., Hertz, A., & de Werra, D. (1987). Some experiments with simulated annealing for coloring graphs. European Journal of Operational Research,32, 260\u2013266.","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"6778_CR14","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1287\/opre.39.3.378","volume":"39","author":"DS Johnson","year":"1991","unstructured":"Johnson, D. S., Aragon, C. R., McGeoch, L. A., & Schevon, C. (1991). Optimization by simulated annealing: An experimental evaluation; Part II, graph coloring and number partitioning. Operations Research,39(3), 378\u2013406.","journal-title":"Operations Research"},{"key":"6778_CR15","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1007\/BFb0056916","volume":"1498","author":"R Dorne","year":"1998","unstructured":"Dorne, R., & Hao, J. K. (1998). A new genetic local search algorithm for graph coloring. Lecture Notes in Computer Science,1498, 745\u2013754.","journal-title":"Lecture Notes in Computer Science"},{"issue":"2","key":"6778_CR16","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/j.dam.2006.07.017","volume":"156","author":"P Galinier","year":"2008","unstructured":"Galinier, P., Hertz, A., & Zufferey, N. (2008). An adaptive memory algorithm for the K-colouring problem. Discrete Applied Mathematics,156(2), 267\u2013279.","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"6778_CR17","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/j.ejor.2008.12.007","volume":"200","author":"Z Lu","year":"2010","unstructured":"Lu, Z., & Hao, J. K. (2010). A memetic algorithm for graph coloring. European Journal of Operational Research,200(1), 235\u2013244.","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"6778_CR18","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1287\/ijoc.1070.0245","volume":"20","author":"E Malaguti","year":"2008","unstructured":"Malaguti, E., Monaci, M., & Toth, P. (2008). A metaheuristic approach for the vertex coloring problem. INFORMS Journal on Computing,20(2), 302\u2013316.","journal-title":"INFORMS Journal on Computing"},{"issue":"9","key":"6778_CR19","doi-asserted-by":"publisher","first-page":"2547","DOI":"10.1016\/j.cor.2005.07.028","volume":"33","author":"P Galinier","year":"2006","unstructured":"Galinier, P., & Hertz, A. (2006). A survey of local search methods for graph coloring. Computers & Operations Research,33(9), 2547\u20132562.","journal-title":"Computers & Operations Research"},{"key":"6778_CR20","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/BF02125407","volume":"63","author":"C Fleurent","year":"1996","unstructured":"Fleurent, C., & Ferland, J. A. (1996). Genetic and hybrid algorithms for graph coloring. Annals of Operations Research,63, 437\u2013461.","journal-title":"Annals of Operations Research"},{"issue":"2","key":"6778_CR21","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/j.cor.2011.04.002","volume":"39","author":"Q Wu","year":"2012","unstructured":"Wu, Q., & Hao, J. K. (2012). Coloring large graphs based on independent set extraction. Computers & Operations Research,39(2), 283\u2013290.","journal-title":"Computers & Operations Research"},{"issue":"16\u201317","key":"6778_CR22","doi-asserted-by":"publisher","first-page":"2397","DOI":"10.1016\/j.dam.2012.06.007","volume":"160","author":"JK Hao","year":"2012","unstructured":"Hao, J. K., & Wu, Q. (2012). Improving the extraction and expansion method for large graph coloring. Discrete Applied Mathematics,160(16\u201317), 2397\u20132407.","journal-title":"Discrete Applied Mathematics"},{"issue":"7","key":"6778_CR23","doi-asserted-by":"publisher","first-page":"1097","DOI":"10.1016\/j.dam.2007.05.058","volume":"156","author":"MB Campelo","year":"2008","unstructured":"Campelo, M. B., Campos, V. A., & Correa, R. C. (2008). On the asymmetric representatives formulation for the vertex coloring problem. Discrete Applied Mathematics,156(7), 1097\u20131111.","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"6778_CR24","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.disopt.2008.10.004","volume":"6","author":"P Hansen","year":"2009","unstructured":"Hansen, P., Labbe, M., & Schindl, D. (2009). Set covering and packing formulation of graph coloring: Algorithms and first polyhedral results. Discrete Optimization,6(2), 135\u2013147.","journal-title":"Discrete Optimization"},{"issue":"2","key":"6778_CR25","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/j.disopt.2010.07.005","volume":"8","author":"E Malaguti","year":"2011","unstructured":"Malaguti, E., Monaci, M., & Toth, P. (2011). An exact approach for the vertex coloring problem. Discrete Optimization,8(2), 174\u2013190.","journal-title":"Discrete Optimization"},{"issue":"1","key":"6778_CR26","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1287\/ijoc.1100.0436","volume":"24","author":"S Gualandi","year":"2012","unstructured":"Gualandi, S., & Malucelli, F. (2012). Exact solution of graph coloring problems via constraint programming and column generation. INFORMS Journal on Computing,24(1), 81\u2013100.","journal-title":"INFORMS Journal on Computing"},{"issue":"3","key":"6778_CR27","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0378-8733(83)90028-X","volume":"5","author":"S Seidman","year":"1983","unstructured":"Seidman, S. (1983). Network structure and minimum degree. Social Networks,5(3), 269\u2013287.","journal-title":"Social Networks"},{"issue":"1","key":"6778_CR28","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/s13278-014-0228-y","volume":"4","author":"RA Rossi","year":"2014","unstructured":"Rossi, R. A., & Ahmed, N. K. (2014). Coloring large complex networks. Social Network Analysis: Mining,4(1), 228\u2013239.","journal-title":"Social Network Analysis: Mining"},{"issue":"1","key":"6778_CR29","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1287\/ijoc.2014.0618","volume":"27","author":"A Verma","year":"2015","unstructured":"Verma, A., Buchanan, A., & Butenko, S. (2015). Solving the maximum clique and vertex coloring problems on very large sparse networks. INFORMS Journal on Computing,27(1), 164\u2013177.","journal-title":"INFORMS Journal on Computing"},{"issue":"5","key":"6778_CR30","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1142\/S0217595913500188","volume":"30","author":"Q Wu","year":"2013","unstructured":"Wu, Q., & Hao, J. K. (2013). An extraction and expansion approach for graph coloring. Asia-Pacific Journal of Operational Research,30(5), 132\u2013147.","journal-title":"Asia-Pacific Journal of Operational Research"},{"key":"6778_CR31","doi-asserted-by":"crossref","unstructured":"Peng, Y., Choi, B., He, B., Zhou, S., Xu, R., & Yu, X. (2016). Vcolor: A practical vertex-cut based approach for coloring large graphs. In 32nd IEEE international conference on data engineering, Helsinki, Finland, May 2016 (pp. 97\u2013108).","DOI":"10.1109\/ICDE.2016.7498232"},{"key":"6778_CR32","doi-asserted-by":"crossref","unstructured":"Lin, J., Cai, S., Luo, C., & Su, K. (2017). A reduction based method for coloring very large graphs. In Proceedings of the twenty-sixth international joint conference on artificial intelligence (IJCAI-17) (pp. 517\u2013523).","DOI":"10.24963\/ijcai.2017\/73"},{"key":"6778_CR33","unstructured":"DIMACS Implementation Challenges. Retrieved from 10 Sept 2016 \nhttp:\/\/dimacs.rutgers.edu\/Challenges\/\n\n."},{"key":"6778_CR34","unstructured":"Graph coloring instances. \nhttp:\/\/mat.gsia.cmu.edu\/COLOR\/instances.html\n\n."},{"issue":"5","key":"6778_CR35","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1016\/j.dam.2005.05.022","volume":"154","author":"I Mendez-Diaz","year":"2006","unstructured":"Mendez-Diaz, I., & Zabala, P. (2006). A branch and cut algorithm for graph coloring. Discrete Applied Mathematics,154(5), 826\u2013847.","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"6778_CR36","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1287\/ijoc.1070.0245","volume":"20","author":"E Malaguti","year":"2008","unstructured":"Malaguti, E., Monaci, M., & Toth, A. (2008). A metaheuristic approach for the vertex coloring problem. INFORMS Journal on Computing,20(2), 302\u2013316.","journal-title":"INFORMS Journal on Computing"}],"container-title":["Wireless Personal Communications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11277-019-06778-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11277-019-06778-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11277-019-06778-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,17]],"date-time":"2020-09-17T12:45:37Z","timestamp":1600346737000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11277-019-06778-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,18]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,2]]}},"alternative-id":["6778"],"URL":"https:\/\/doi.org\/10.1007\/s11277-019-06778-0","relation":{},"ISSN":["0929-6212","1572-834X"],"issn-type":[{"value":"0929-6212","type":"print"},{"value":"1572-834X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,18]]},"assertion":[{"value":"18 September 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}