{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T07:58:51Z","timestamp":1761897531056},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,4,16]],"date-time":"2021-04-16T00:00:00Z","timestamp":1618531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,4,16]],"date-time":"2021-04-16T00:00:00Z","timestamp":1618531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Front. Comput. Sci."],"published-print":{"date-parts":[[2021,8]]},"DOI":"10.1007\/s11704-020-9205-y","type":"journal-article","created":{"date-parts":[[2021,4,16]],"date-time":"2021-04-16T05:25:20Z","timestamp":1618550720000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["VColor*: a practical approach for coloring large graphs"],"prefix":"10.1007","volume":"15","author":[{"given":"Yun","family":"Peng","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xin","family":"Lin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Byron","family":"Choi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bingsheng","family":"He","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,4,16]]},"reference":[{"key":"9205_CR1","doi-asserted-by":"crossref","unstructured":"Peng Y, Choi B, He B, Zhou S, Xu R, Yu X. Vcolor: a practical vertex-cut based approach for coloring large graphs. In: Proceedings of IEEE International Conference on Data Engineering. 2016, 97\u2013108","DOI":"10.1109\/ICDE.2016.7498232"},{"key":"9205_CR2","unstructured":"Ingrid A. Nucleic acid sequence design as a graph colouring problem. Thesis, Universitat Wien, 2005, 1\u201383"},{"issue":"2","key":"9205_CR3","first-page":"258","volume":"39","author":"T Park","year":"1996","unstructured":"Park T, Lee C Y. Application of the graph coloring algorithm to the frequency assignment problem. Journal of the Operations Research of Japan, 1996, 39(2): 258\u2013265","journal-title":"Journal of the Operations Research of Japan"},{"issue":"6","key":"9205_CR4","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1145\/872726.806984","volume":"17","author":"G Chaitin","year":"1982","unstructured":"Chaitin G. Register allocation and spilling via graph coloring. ACM Sigplan Notices, 1982, 17(6): 98\u2013101","journal-title":"ACM Sigplan Notices"},{"issue":"1","key":"9205_CR5","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0305-0548(86)90061-4","volume":"13","author":"V Lotfi","year":"1986","unstructured":"Lotfi V, Sarin S. A graph coloring algorithm for large scale scheduling problems. Computers & Operations Research, 1986, 13(1): 27\u201332","journal-title":"Computers & Operations Research"},{"key":"9205_CR6","doi-asserted-by":"crossref","unstructured":"Moradi F, Olovsson T, Tsigas P. A local seed selection algorithm for overlapping community detection. In: Proceedings of IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining. 2014, 1\u20138","DOI":"10.1109\/ASONAM.2014.6921552"},{"key":"9205_CR7","doi-asserted-by":"crossref","unstructured":"Yuan L, Qin L, Lin X, Chang L, Zhang W. Diversified top-k clique search. In: Proceedings of IEEE International Conference on Data Engineering. 2015, 387\u2013398","DOI":"10.1109\/ICDE.2015.7113300"},{"issue":"4","key":"9205_CR8","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/BF02239976","volume":"39","author":"A Hertz","year":"1987","unstructured":"Hertz A, De Werra D. Using tabu search techniques for graph coloring. Computing, 1987, 39(4): 345\u2013351","journal-title":"Computing"},{"issue":"1","key":"9205_CR9","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0020-0190(93)90246-6","volume":"45","author":"M M Halld\u00c3\u015frsson","year":"1993","unstructured":"Halld\u00c3\u015frsson M M. A still better performance guarantee for approximate graph coloring. Information Processing Letters, 1993, 45(1): 19\u201323","journal-title":"Information Processing Letters"},{"issue":"4","key":"9205_CR10","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1023\/A:1009823419804","volume":"3","author":"P Galinier","year":"1999","unstructured":"Galinier P, Hao J K. Hybrid evolutionary algorithms for graph coloring. Journal of Combinatorial Optimization, 1999, 3(4): 379\u2013397","journal-title":"Journal of Combinatorial Optimization"},{"key":"9205_CR11","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/978-3-642-30504-7_20","volume":"1","author":"P Galinier","year":"2013","unstructured":"Galinier P, Hamiez J P, Hao J K, Porumbel D. Recent advances in graph vertex coloring. Handbook of Optimization, 2013, 1: 505\u2013528","journal-title":"Handbook of Optimization"},{"issue":"2","key":"9205_CR12","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1145\/274787.274791","volume":"45","author":"D Karger","year":"1998","unstructured":"Karger D, Motwani R, Sudan M. Approximate graph coloring by semidefinite programming. Journal of the ACM, 1998, 45(2): 246\u2013265","journal-title":"Journal of the ACM"},{"key":"9205_CR13","doi-asserted-by":"crossref","unstructured":"Pardalos P M, Mavridou T, Xue J. The Graph Coloring Problem: a Bibliographic Survey. Handbook of Combinatorial Optimization, Springer, Boston, 1999, 1077\u20131141","DOI":"10.1007\/978-1-4613-0303-9_16"},{"key":"9205_CR14","doi-asserted-by":"crossref","unstructured":"Husfeldt T. Graph Colouring Algorithms. Cambridge University Press, 2015, 277\u2013303","DOI":"10.1017\/CBO9781139519793.016"},{"key":"9205_CR15","doi-asserted-by":"crossref","unstructured":"Kuhn F, Wattenhofer R. On the complexity of distributed graph coloring. In: Proceedings of ACM Symposium on Principles of Distributed Computing. 2006, 7\u201315","DOI":"10.1145\/1146381.1146387"},{"issue":"4","key":"9205_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1597036.1597042","volume":"5","author":"D Eppstein","year":"2009","unstructured":"Eppstein D. All maximal independent sets and dynamic dominance for sparse graphs. ACM Transactions on Algorithms, 2009, 5(4): 1\u201314","journal-title":"ACM Transactions on Algorithms"},{"issue":"6","key":"9205_CR17","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1016\/j.orl.2004.03.002","volume":"32","author":"J M Byskov","year":"2004","unstructured":"Byskov J M. Enumerating maximal independent sets with applications to graph colouring. Operations Research Letters, 2004, 32(6): 547\u2013556","journal-title":"Operations Research Letters"},{"key":"9205_CR18","doi-asserted-by":"crossref","unstructured":"Feige U, Mahdian M. Finding small balanced separators. In: Proceedings of the Annual ACM Symposium on Theory of Computing. 2006, 375\u2013384","DOI":"10.1145\/1132516.1132573"},{"key":"9205_CR19","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/026","volume-title":"Cliques, Coloring, and Satisfiability","author":"D J Johnson","year":"1996","unstructured":"Johnson D J, Trick M A. Cliques, Coloring, and Satisfiability. Boston, MA, USA: American Mathematical Society, 1996"},{"issue":"2","key":"9205_CR20","doi-asserted-by":"publisher","first-page":"133","DOI":"10.14778\/2535568.2448946","volume":"6","author":"J Lee","year":"2012","unstructured":"Lee J, Han W S, Kasperovics R, Lee J H. An in-depth comparison of subgraph isomorphism algorithms in graph databases. Proceedings of the VLDB Endowment, 2012, 6(2): 133\u2013144","journal-title":"Proceedings of the VLDB Endowment"},{"issue":"3","key":"9205_CR21","doi-asserted-by":"publisher","first-page":"654","DOI":"10.1137\/0914041","volume":"14","author":"M T Jones","year":"1993","unstructured":"Jones M T, Plassmann P E. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, 1993, 14(3): 654\u2013669","journal-title":"SIAM Journal on Scientific Computing"},{"issue":"7","key":"9205_CR22","doi-asserted-by":"publisher","first-page":"577","DOI":"10.14778\/2732286.2732294","volume":"7","author":"S Salihoglu","year":"2014","unstructured":"Salihoglu S, Widom J. Optimizing graph algorithms on pregel-like systems. Proceedings of the VLDB Endowment, 2014, 7(7): 577\u2013588","journal-title":"Proceedings of the VLDB Endowment"},{"issue":"2","key":"9205_CR23","doi-asserted-by":"publisher","first-page":"338","DOI":"10.14778\/3157794.3157802","volume":"11","author":"L Yuan","year":"2017","unstructured":"Yuan L, Qin L, Lin X, Chang L, Zhang W. Effective and efficient dynamic graphcoloring. Proceedings of the VLDB Endowment, 2017, 11(2): 338\u2013351","journal-title":"Proceedings of the VLDB Endowment"},{"issue":"4","key":"9205_CR24","doi-asserted-by":"publisher","first-page":"1319","DOI":"10.1007\/s00453-018-0473-y","volume":"81","author":"L Barba","year":"2019","unstructured":"Barba L, Cardinal J, Korman M, Langerman S, Renssen V A, Roeloffzen M, Verdonschot S. Dynamic graph coloring. Algorithmica, 2019, 81(4): 1319\u20131341","journal-title":"Algorithmica"},{"issue":"3","key":"9205_CR25","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1016\/j.cor.2006.05.014","volume":"35","author":"I Bl\u00f6chliger","year":"2008","unstructured":"Bl\u00f6chliger I, Zufferey N. A graph coloring heuristic using partial solutions and a reactive tabu scheme. Computers & Operations Research, 2008, 35(3): 960\u2013975","journal-title":"Computers & Operations Research"},{"key":"9205_CR26","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1007\/978-3-540-79305-2_11","volume":"1","author":"D Porumbel","year":"2008","unstructured":"Porumbel D, Hao J K, Kuntz P. A study of evaluation functions for the graph k-coloring problem. Artificial Evolution, 2008, 1: 124\u2013135","journal-title":"Artificial Evolution"},{"issue":"13","key":"9205_CR27","doi-asserted-by":"publisher","first-page":"2551","DOI":"10.1016\/j.dam.2008.03.022","volume":"156","author":"A Hertz","year":"2008","unstructured":"Hertz A, Plumettaz M, Zufferey N. Variable space search for graph coloring. Discrete Applied Mathematics, 2008, 156(13): 2551\u20132560","journal-title":"Discrete Applied Mathematics"},{"key":"9205_CR28","unstructured":"Morgenstern C, Shapiro H. Coloration neighborhood structures for general graph coloring. In: Proceedings of Annual ACM-SIAM Symposium on Discrete Algorithms. 1990, 226\u2013235"},{"issue":"3","key":"9205_CR29","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/BF02125407","volume":"63","author":"C Fleurent","year":"1996","unstructured":"Fleurent C, Ferland J. Genetic and hybrid algorithms for graph coloring. Annals of Operations Research, 1996, 63(3): 437\u2013461","journal-title":"Annals of Operations Research"},{"issue":"2","key":"9205_CR30","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. An adaptive memory algorithm for the k-coloring problem. Discrete Applied Mathematics, 2008, 156(2): 267\u2013279","journal-title":"Discrete Applied Mathematics"},{"issue":"10","key":"9205_CR31","doi-asserted-by":"publisher","first-page":"1822","DOI":"10.1016\/j.cor.2010.01.015","volume":"37","author":"D C Porumbel","year":"2010","unstructured":"Porumbel D C, Hao J K, Kuntz P. An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring. Computers & Operations Research, 2010, 37(10): 1822\u20131832","journal-title":"Computers & Operations Research"},{"issue":"1","key":"9205_CR32","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/j.ejor.2009.07.016","volume":"203","author":"Z L\u00fc","year":"2010","unstructured":"L\u00fc Z, Hao J K. A memetic algorithm for graph coloring. European Journal of Operational Research, 2010, 203(1): 241\u2013250","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"9205_CR33","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. Some experiments with simulated annealing for coloring graphs. European Journal of Operational Research, 1987, 32(2): 260\u2013266","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"9205_CR34","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1287\/opre.39.3.378","volume":"39","author":"D S Johnson","year":"1991","unstructured":"Johnson D S, Aragon C R, McGeoch L A, Schevon C. Optimization by simulated annealing: an experimental evaluation; part ii, graph coloring and number partitioning. Operations Research, 1991, 39(3): 378\u2013406","journal-title":"Operations Research"},{"issue":"2","key":"9205_CR35","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. Coloring large graphs based on independent set extraction. Computers & Operations Research, 2012, 39(2): 283\u2013290","journal-title":"Computers & Operations Research"},{"issue":"5","key":"9205_CR36","doi-asserted-by":"publisher","first-page":"1350018","DOI":"10.1142\/S0217595913500188","volume":"30","author":"Q Wu","year":"2013","unstructured":"Wu Q, Hao J K. An extraction and expansion approach for graph coloring. Asia-Pacific Journal of Operational Research, 2013, 30(5): 1350018","journal-title":"Asia-Pacific Journal of Operational Research"},{"issue":"16\u201317","key":"9205_CR37","doi-asserted-by":"publisher","first-page":"2397","DOI":"10.1016\/j.dam.2012.06.007","volume":"160","author":"J K Hao","year":"2012","unstructured":"Hao J K, Wu Q. Improving the extraction and expansion method for large graph coloring. Discrete Applied Mathematics, 2012, 160(16\u201317): 2397\u20132407","journal-title":"Discrete Applied Mathematics"},{"key":"9205_CR38","doi-asserted-by":"crossref","unstructured":"Schneider J, Wattenhofer R. A new technique for distributed symmetry breaking. In: Proceedings of ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. 2010, 257\u2013266","DOI":"10.1145\/1835698.1835760"},{"key":"9205_CR39","doi-asserted-by":"crossref","unstructured":"Luby M. A simple parallel algorithm for the maximal independent set problem. In: Proceedings of Annual ACM Symposium on Theory of Computing. 1985, 1\u201310","DOI":"10.1145\/22145.22146"},{"issue":"1","key":"9205_CR40","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","volume":"70","author":"R Cole","year":"1986","unstructured":"Cole R, Vishkin U. Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control, 1986, 70(1): 32\u201353","journal-title":"Information and Control"},{"issue":"1","key":"9205_CR41","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N Linial","year":"1992","unstructured":"Linial N. Locality in distributed graph algorithms. SIAM Journal on Computing, 1992, 21(1): 193\u2013201","journal-title":"SIAM Journal on Computing"},{"key":"9205_CR42","doi-asserted-by":"crossref","unstructured":"Szegedy M, Vishwanathan S. Locality based graph coloring. In: Proceedings of ACM Symposium on Theory of Computing. 1993, 201\u2013207","DOI":"10.1145\/167088.167156"},{"key":"9205_CR43","doi-asserted-by":"crossref","unstructured":"Panconesi A, Srinivasan A. On the Complexity of Distributed Network Decomposition. Academic Press, Inc., 1996","DOI":"10.1006\/jagm.1996.0017"},{"issue":"1","key":"9205_CR44","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1137\/12088848X","volume":"43","author":"L Barenboim","year":"2014","unstructured":"Barenboim L, Elkin M, Kuhn F. Distributed (delta + 1)-coloring in linear (in delta) time. Siam Journal on Computing, 2014, 43(1): 72\u201395","journal-title":"Siam Journal on Computing"},{"issue":"6","key":"9205_CR45","doi-asserted-by":"publisher","first-page":"3628","DOI":"10.1109\/TNET.2017.2751544","volume":"25","author":"A Checco","year":"2017","unstructured":"Checco A, Leith D J. Fast, responsive decentralized graph coloring. IEEE\/ACM Transactions on Networking, 2017, 25(6): 3628\u20133640","journal-title":"IEEE\/ACM Transactions on Networking"}],"container-title":["Frontiers of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-020-9205-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11704-020-9205-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-020-9205-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,19]],"date-time":"2022-09-19T20:42:44Z","timestamp":1663620164000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11704-020-9205-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,16]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["9205"],"URL":"https:\/\/doi.org\/10.1007\/s11704-020-9205-y","relation":{},"ISSN":["2095-2228","2095-2236"],"issn-type":[{"value":"2095-2228","type":"print"},{"value":"2095-2236","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,16]]},"assertion":[{"value":"5 June 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 April 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 May 2021","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The corresponding author Yun Peng is incorrect, it should be Xin Lin.","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"154610"}}