{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,21]],"date-time":"2024-09-21T04:27:39Z","timestamp":1726892859421},"reference-count":26,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Fundamentals"],"published-print":{"date-parts":[[2022,9,1]]},"DOI":"10.1587\/transfun.2021dmp0011","type":"journal-article","created":{"date-parts":[[2022,3,17]],"date-time":"2022-03-17T22:09:27Z","timestamp":1647554967000},"page":"1241-1251","source":"Crossref","is-referenced-by-count":0,"title":["Speeding-Up Construction Algorithms for the Graph Coloring Problem"],"prefix":"10.1587","volume":"E105.A","author":[{"given":"Kazuho","family":"KANAHARA","sequence":"first","affiliation":[{"name":"Department of Information and Computer Engineering, Okayama University of Science"}]},{"given":"Kengo","family":"KATAYAMA","sequence":"additional","affiliation":[{"name":"Department of Information and Computer Engineering, Okayama University of Science"}]},{"given":"Etsuji","family":"TOMITA","sequence":"additional","affiliation":[{"name":"The Advanced Algorithms Research Laboratory, The University of Electro-Communications"}]}],"member":"532","reference":[{"key":"1","unstructured":"[1] https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/imada.sdu.dk\/~marco\/gcp-study\/"},{"key":"2","unstructured":"[2] https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/imada.sdu.dk\/~marco\/gcp\/rlf\/"},{"key":"3","doi-asserted-by":"publisher","unstructured":"[3] M. Adegbindin, A. Hertz, and M. Bella\u00efche, \u201cA new efficient RLF-like algorithm for the vertex coloring problem,\u201d Yugoslav J. Oper. Res., vol.26, no.4, pp.441-456, 2016. 10.2298\/yjor151102003a","DOI":"10.2298\/YJOR151102003A"},{"key":"4","unstructured":"[4] B. Balabhaskar and B. Sergiy, \u201cGraph domination, coloring and cliques in telecommunications,\u201d Handbook of Optimization in Telecommunications, pp.865-890. Springer, 2006. 10.1007\/978-0-387-30165-5_30"},{"key":"5","doi-asserted-by":"publisher","unstructured":"[5] R. Battiti and A.A. Bertossi, \u201cGreedy, prohibition, and reactive heuristics for graph partitioning,\u201d IEEE Trans. Comput., vol.48, no.4, pp.361-385, 1999. 10.1109\/12.762522","DOI":"10.1109\/12.762522"},{"key":"6","doi-asserted-by":"publisher","unstructured":"[6] R. Battiti and M. Protasi, \u201cReactive local search for the maximum clique problem,\u201d Algorithmica, vol.29, no.4, pp.610-637, 2001. 10.1007\/s004530010074","DOI":"10.1007\/s004530010074"},{"key":"7","doi-asserted-by":"publisher","unstructured":"[7] E.A. Bender and H.S. Wilf, \u201cA theoretical analysis of backtracking in the graph coloring problem,\u201d J. Algorithms, vol.6, no.2, pp.275-282, 1985. 10.1016\/0196-6774(85)90044-6","DOI":"10.1016\/0196-6774(85)90044-6"},{"key":"8","doi-asserted-by":"crossref","unstructured":"[8] C. Blum and G.R. Raidl, Hybrid Metaheuristics: Powerful Tools for Optimization, 1st ed., Springer, 2016.","DOI":"10.1007\/978-3-319-30883-8_1"},{"key":"9","doi-asserted-by":"publisher","unstructured":"[9] D. Br\u00e9laz, \u201cNew methods to color the vertices of a graph,\u201d Commun. ACM, vol.22, no.4, pp.251-256, 1979. 10.1145\/359094.359101","DOI":"10.1145\/359094.359101"},{"key":"10","doi-asserted-by":"crossref","unstructured":"[10] L.C.-Min, F. Zhiwen, J. Hua, and X. Ke, \u201cIncremental upper bound for the maximum clique problem,\u201d Informs J. Comput., vol.30, no.1, pp.137-153, 2018. 10.1287\/ijoc.2017.0770","DOI":"10.1287\/ijoc.2017.0770"},{"key":"11","doi-asserted-by":"crossref","unstructured":"[11] G.J. Chaitin, \u201cRegister allocation &amp; spilling via graph coloring,\u201d Proc. 1982 SIGPLAN Symposium on Compiler Construction, SIGPLAN&apos;82, pp.98-105, 1982. 10.1145\/800230.806984","DOI":"10.1145\/800230.806984"},{"key":"12","unstructured":"[12] M. Chiarandini, G. Galbiati, and S. Gualandi, \u201cEfficiency issues in the RLF heuristic for graph coloring,\u201d Proc. 9th Metaheuristics International Conference, MIC 2011, pp.461-469, 2011."},{"key":"13","doi-asserted-by":"crossref","unstructured":"[13] T. Dimitris, L. Eirini, P. Nikos, and M. Lazaros, \u201cA graph-coloring secondary resource allocation for D2D communications in LTE networks,\u201d 2012 IEEE 17th International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD), pp.56-60. IEEE, 2012. 10.1109\/camad.2012.6335378","DOI":"10.1109\/CAMAD.2012.6335378"},{"key":"14","doi-asserted-by":"crossref","unstructured":"[14] P. Erd\u00f6s and A. R\u00e9nyi, \u201cOn random graphs I,\u201d Publicationes Mathematicae Debrecen, vol.6, pp.290-297, 1959.","DOI":"10.5486\/PMD.1959.6.3-4.12"},{"key":"15","doi-asserted-by":"publisher","unstructured":"[15] F. Furini, V. Gabrel, and I.-C. Ternier, \u201cAn improved DSATUR-based branch and bound algorithm for the vertex coloring problem,\u201d Networks, vol.69, no.1, pp.124-141, 2017. 10.1002\/net.21716","DOI":"10.1002\/net.21716"},{"key":"16","doi-asserted-by":"publisher","unstructured":"[16] P. Galinier and A. Hertz, \u201cA survey of local search methods for graph coloring,\u201d Comput. Oper. Res., vol.33, no.9, pp.2547-2562, 2006. 10.1016\/j.cor.2005.07.028","DOI":"10.1016\/j.cor.2005.07.028"},{"key":"17","unstructured":"[17] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979."},{"key":"18","doi-asserted-by":"publisher","unstructured":"[18] W.K. Hale, \u201cFrequency assignment: Theory and applications,\u201d Proc. IEEE, vol.68, no.12, pp.1497-1514, 1980. 10.1109\/proc.1980.11899","DOI":"10.1109\/PROC.1980.11899"},{"key":"19","doi-asserted-by":"publisher","unstructured":"[19] D.S. Johnson, C.R. Aragon, L.A. McGeoch, and C. Schevon, \u201cOptimization by simulated annealing: An experimental evaluation; part II, graph coloring and number partitioning,\u201d Oper. Res., vol.39, no.3, pp.378-406, 1991. 10.1287\/opre.39.3.378","DOI":"10.1287\/opre.39.3.378"},{"key":"20","doi-asserted-by":"publisher","unstructured":"[21] P.V. Khuong and P. Morin, \u201cArray layouts for comparison-based searching,\u201d ACM J. Exp. Algorithmics, vol.22, pp.1-39, May 2017. 10.1145\/3053370","DOI":"10.1145\/3053370"},{"key":"21","doi-asserted-by":"crossref","unstructured":"[22] F.T. Leighton, \u201cA graph coloring algorithm for large scheduling problems,\u201d J. Res. Nat. Bur. Stand., vol.84, no.6, pp.489-506, 1979. 10.6028\/jres.084.024","DOI":"10.6028\/jres.084.024"},{"key":"22","doi-asserted-by":"crossref","unstructured":"[23] D.R. Musser, \u201cIntrospective sorting and selection algorithms,\u201d Software: Pract. Exper., vol.27, no.8, pp.983-993, 1997. 10.1002\/(SICI)1097-024X(199708)27:8%3C983::AID-SPE117%3E3.0.CO;2-%23","DOI":"10.1002\/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#"},{"key":"23","doi-asserted-by":"publisher","unstructured":"[24] M.G.C. Resende and R.F. Werneck, \u201cA fast swap-based local search procedure for location problems,\u201d Ann. Oper. Res., vol.150, no.1, pp.205-230, 2007. 10.1007\/s10479-006-0154-0","DOI":"10.1007\/s10479-006-0154-0"},{"key":"24","unstructured":"[25] E. Tomita, J. Yanagisawa, K. Katayama, K. Kanahara, T. Toda, H. Ito, M. Wakatsuki, and T. Nishino, \u201cAn improved branch-and-bound MCT algorithm for finding a maximum clique,\u201d Springer Nature (to appear). The preliminary version was published in IPSJ SIG Technical Report, vol.2021-MPS-134, no.3, pp.1-4, 2021."},{"key":"25","doi-asserted-by":"crossref","unstructured":"[26] E. Tomita, K. Yoshida, T. Hatta, A. Nagao, H. Ito, and M. Wakatsuki, \u201cA much faster algorithm for finding a maximum clique,\u201d Frontiers in Algorithmics, Lecture Notes in Computer Science, vol.9711, pp.215-226, 2016. 10.1007\/978-3-319-39817-4_21","DOI":"10.1007\/978-3-319-39817-4_21"},{"key":"26","doi-asserted-by":"publisher","unstructured":"[27] H.S. Wilf, \u201cBacktrack: An O(1) expected time algorithm for the graph coloring problem,\u201d Inform. Process. Lett., vol.18, no.3, pp.119-121, 1984. 10.1016\/0020-0190(84)90013-9","DOI":"10.1016\/0020-0190(84)90013-9"}],"container-title":["IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/www.jstage.jst.go.jp\/article\/transfun\/E105.A\/9\/E105.A_2021DMP0011\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,20]],"date-time":"2024-09-20T14:04:18Z","timestamp":1726841058000},"score":1,"resource":{"primary":{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/www.jstage.jst.go.jp\/article\/transfun\/E105.A\/9\/E105.A_2021DMP0011\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,1]]},"references-count":26,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2022]]}},"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.1587\/transfun.2021dmp0011","relation":{},"ISSN":["0916-8508","1745-1337"],"issn-type":[{"type":"print","value":"0916-8508"},{"type":"electronic","value":"1745-1337"}],"subject":[],"published":{"date-parts":[[2022,9,1]]},"article-number":"2021DMP0011"}}