{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T01:46:20Z","timestamp":1773798380421,"version":"3.50.1"},"reference-count":40,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Fundamentals"],"published-print":{"date-parts":[[2024,1,1]]},"DOI":"10.1587\/transfun.2023kep0003","type":"journal-article","created":{"date-parts":[[2023,9,11]],"date-time":"2023-09-11T22:28:21Z","timestamp":1694471301000},"page":"38-51","source":"Crossref","is-referenced-by-count":4,"title":["Ising-Machine-Based Solver for Constrained Graph Coloring Problems"],"prefix":"10.1587","volume":"E107.A","author":[{"given":"Soma","family":"KAWAKAMI","sequence":"first","affiliation":[{"name":"Department of Computer Science and Communications Engineering, Waseda University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yosuke","family":"MUKASA","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Communications Engineering, Waseda University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Siya","family":"BAO","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Communications Engineering, Waseda University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dema","family":"BA","sequence":"additional","affiliation":[{"name":"NTT Computer and Data Science Laboratories, Nippon Telegraph and Telephone Corporation"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Junya","family":"ARAI","sequence":"additional","affiliation":[{"name":"NTT Computer and Data Science Laboratories, Nippon Telegraph and Telephone Corporation"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Satoshi","family":"YAGI","sequence":"additional","affiliation":[{"name":"NTT Computer and Data Science Laboratories, Nippon Telegraph and Telephone Corporation"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Junji","family":"TERAMOTO","sequence":"additional","affiliation":[{"name":"NTT Computer and Data Science Laboratories, Nippon Telegraph and Telephone Corporation"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nozomu","family":"TOGAWA","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Communications Engineering, Waseda University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"[1] M. J\u00fcnger, G. Reinelt, and G. Rinaldi, \u201cThe traveling salesman problem,\u201d Handbooks in Operation Research and Management Science, vol.7, pp.225-330, 1995. 10.1016\/s0927-0507(05)80121-5","DOI":"10.1016\/S0927-0507(05)80121-5"},{"key":"2","doi-asserted-by":"publisher","unstructured":"[2] H.M. Salkin and C.A. De Kluyver, \u201cThe knapsack problem: A survey,\u201d Naval Research Logistics Quarterly, vol.22, no.1, pp.127-144, 1975. 10.1002\/nav.3800220110","DOI":"10.1002\/nav.3800220110"},{"key":"3","doi-asserted-by":"publisher","unstructured":"[3] Y. Fu and P.W. Anderson, \u201cApplication of statistical mechanics to NP-complete problems in combinatorial optimisation,\u201d J. Phys. A: Math. Gen., vol.19, no.9, pp.1605-1620, 1986. 10.1088\/0305-4470\/19\/9\/033","DOI":"10.1088\/0305-4470\/19\/9\/033"},{"key":"4","doi-asserted-by":"crossref","unstructured":"[4] F. Glover, \u201cTabu search \u2014 Part I,\u201d ORSA Journal on Computing, vol.1, no.3, pp.190-206, 1989. 10.1287\/ijoc.1.3.190","DOI":"10.1287\/ijoc.1.3.190"},{"key":"5","doi-asserted-by":"publisher","unstructured":"[5] F. Glover, \u201cTabu search \u2014 Part II,\u201d ORSA Journal on Computing, vol.2, no.1, pp.4-32, 1990. 10.1287\/ijoc.2.1.4","DOI":"10.1287\/ijoc.2.1.4"},{"key":"6","unstructured":"[6] P. Hansen, \u201cThe steepest ascent mildest descent heuristic for combinatorial programming,\u201d Congress on Numerical Methods in Combinatorial Optimization, Capri, Italy, 1986."},{"key":"7","doi-asserted-by":"crossref","unstructured":"[7] S. Kirkpatrick, C.D. Gelatt, Jr., and M.P. Vecchi, \u201cOptimization by simulated annealing,\u201d Science, vol.220, no.4598, pp.671-680, 1983. 10.1126\/science.220.4598.671","DOI":"10.1126\/science.220.4598.671"},{"key":"8","doi-asserted-by":"crossref","unstructured":"[8] J.H. Holland, Adaptation in Natural and Artificial Systems, MIT Press, 1992. 10.7551\/mitpress\/1090.001.0001","DOI":"10.7551\/mitpress\/1090.001.0001"},{"key":"9","unstructured":"[9] I. Rechenberg, \u201cEvolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution,\u201d Frommann Holzboog Verlag, Stuttgart, 1973."},{"key":"10","unstructured":"[10] M. Dorigo, \u201cOptimization, learning and natural algorithms,\u201d Ph.D. Thesis, Politecnico di Milano, 1992."},{"key":"11","doi-asserted-by":"crossref","unstructured":"[11] M.W. Johnson, M.H.S. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A.J. Berkley, J. Johansson, P. Bunyk, E.M. Chapple, C. Enderud, J.P. Hilton, K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Oh, I. Perminov, C. Rich, M.C. Thom, E. Tolkacheva, C.J.S. Truncik, S. Uchaikin, J. Wang, B. Wilson, and G. Rose, \u201cQuantum annealing with manufactured spins,\u201d Nature, vol.473, no.7346, pp.194-198, 2011. 10.1038\/nature10012","DOI":"10.1038\/nature10012"},{"key":"12","doi-asserted-by":"crossref","unstructured":"[12] C.C. McGeoch and C. Wang, \u201cExperimental evaluation of an adiabiatic quantum system for combinatorial optimization,\u201d Proc. ACM International Conference on Computing Frontiers, pp.1-11, 2013. 10.1145\/2482767.2482797","DOI":"10.1145\/2482767.2482797"},{"key":"13","unstructured":"[13] D-Wave Systems Inc., \u201cAdvantage\u2122,\u201d [Online] Available: https:\/\/www.dwavesys.com\/solutions-and-products\/systems\/"},{"key":"14","doi-asserted-by":"crossref","unstructured":"[14] M. Yamaoka, C. Yoshimura, M. Hayashi, T. Okuyama, H. Aoke, and H. Mizuno, \u201cA 20k-spin Ising chip to solve combitionatorial optimization problems with CMOS annealing,\u201d IEEE J. Solid-State Circuits, vol.51, no.1, pp.303-309, 2015. 10.1109\/JSSC.2015.2498601","DOI":"10.1109\/JSSC.2015.2498601"},{"key":"15","unstructured":"[15] S. Tsukamoto, M. Takatsu, S. Matsubara, and H. Tamura, \u201cAn accelerator architecture for combinatorial optimization problems,\u201d Fujitsu Sci. Tech. J, vol.53, no.5, pp.8-13, 2017."},{"key":"16","doi-asserted-by":"crossref","unstructured":"[16] S. Matsubara, M. Takatsu, T. Miyazawa, T. Shibasaki, Y. Watanabe, K. Takemoto, and H. Tamura \u201cDigital annealer for high-speed solving of combinatorial optimization problems and its applications,\u201d Proc. IEEE\/ACM 2020 25th Asia and South Pacific Design Automation Conference, pp.667-672, 2020. 10.1109\/asp-dac47756.2020.9045100","DOI":"10.1109\/ASP-DAC47756.2020.9045100"},{"key":"17","unstructured":"[17] Fixstars Corporation, \u201cFixstars Amplify AE,\u201d 2020. Available: https:\/\/amplify.fixstars.com\/en\/engine"},{"key":"18","doi-asserted-by":"publisher","unstructured":"[18] H. Goto, K. Tatsumura, and A.R. Dixon, \u201cCombinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems,\u201d Science Advances, vol.5, no.4, eaav2372, 2019. 10.1126\/sciadv.aav2372","DOI":"10.1126\/sciadv.aav2372"},{"key":"19","doi-asserted-by":"publisher","unstructured":"[19] H. Goto, K. Endo, M. Suzuki, Y. Sakai, T. Kanao, Y. Hamakawa, R. Hidaka, M. Yamasaki, and K. Tatsumura, \u201cHigh-performance combinatorial optimization based on classical mechanics,\u201d Science Advances, vol.7, no.6, eabe7953, 2021. 10.1126\/sciadv.abe7953","DOI":"10.1126\/sciadv.abe7953"},{"key":"20","doi-asserted-by":"crossref","unstructured":"[20] T. Inagaki, Y. Haribara, K. Igarashi, T. Sonobe, S. Tamate, T. Honjo, A. Marandi, P.L. McMahon, T. Umeki, K. Enbutsu, O. Tadanaga, H. Takenouchi, K. Aihara, K.-I. Kawarabayashi, K. Inoue, S. Utsunomiya, and H. Takesue, \u201cA coherent Ising machine for 2000-node optimization problems,\u201d Science, vol.354, no.6312, pp.603-606, 2016. 10.1126\/science.aah4243","DOI":"10.1126\/science.aah4243"},{"key":"21","doi-asserted-by":"publisher","unstructured":"[21] T. Honjo, T. Sonobe, K. Inaba, T. Inagaki, T. Ikuta, Y. Yamada, T. Kazama, K. Enbutsu, T. Umeki, R. Kasahara, K.-I. Kawarabayashi, and H. Takesue, \u201c100,000-spin coherent Ising machine,\u201d Science Advances, vol.7, no.40, 2021. 10.1126\/sciadv.abh0952","DOI":"10.1126\/sciadv.abh0952"},{"key":"22","doi-asserted-by":"publisher","unstructured":"[22] R. Marto\u0148\u00e1k, G.E. Santoro, and E. Tosatti, \u201cQuantum annealing of the traveling-salesman problem,\u201d Phys. Rev. E, vol.70, no.5, 057701, 2004. 10.1103\/physreve.70.057701","DOI":"10.1103\/PhysRevE.70.057701"},{"key":"23","doi-asserted-by":"crossref","unstructured":"[23] H. Irie, G. Wongpaisarnsin, M. Terabe, A. Miki, and S. Taguchi, \u201cQuantum annealing of vehicle routing problem with time, state and capacity,\u201d International Workshop on Quantum Technology and Optimization Problems, pp.145-156, 2019. 10.1007\/978-3-030-14082-3_13","DOI":"10.1007\/978-3-030-14082-3_13"},{"key":"24","doi-asserted-by":"publisher","unstructured":"[24] E. Ising, \u201cBeitrag zur Theorie des Ferromagnetismus,\u201d Zeitschrift f\u00fcr Physik, vol.31, no.1, pp.253-258, 1925. 10.1007\/bf02980577","DOI":"10.1007\/BF02980577"},{"key":"25","doi-asserted-by":"publisher","unstructured":"[25] A. S\u00e1nchez-Arroyo, \u201cDetermining the total colouring number is NP-hard,\u201d Discrete Mathematics, vol.78, no.3, pp.315-319, 1989. 10.1016\/0012-365x(89)90187-8","DOI":"10.1016\/0012-365X(89)90187-8"},{"key":"26","unstructured":"[26] S. Ahmed, \u201cApplications of graph coloring in modern computer science,\u201d International Journal of Computer and Information Technology, vol.3, no.2, pp.1-7, 2012."},{"key":"27","doi-asserted-by":"publisher","unstructured":"[28] 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":"28","doi-asserted-by":"crossref","unstructured":"[29] F.T. Leighton, \u201cA graph coloring algorithm for large scheduling problems,\u201d Journal of Research of the National Bureau of Standards, vol.84, no.6, p.489, 1979. 10.6028\/jres.084.024","DOI":"10.6028\/jres.084.024"},{"key":"29","doi-asserted-by":"publisher","unstructured":"[30] A. Hertz and D. de Werra, \u201cUsing tabu search techniques for graph coloring,\u201d Computing, vol.39, no.4, pp.345-351, 1987. 10.1007\/bf02239976","DOI":"10.1007\/BF02239976"},{"key":"30","doi-asserted-by":"publisher","unstructured":"[31] I. Bl\u00f6chliger and N. Zufferey, \u201cA graph coloring heuristic using partial solutions and a reactive tabu scheme,\u201d Computers & Operations Research, vol.35, no.3, pp.960-975, 2008. 10.1016\/j.cor.2006.05.014","DOI":"10.1016\/j.cor.2006.05.014"},{"key":"31","doi-asserted-by":"publisher","unstructured":"[32] A. Lucas, \u201cIsing formulations of many NP problems,\u201d Front. Phys., vol.2, no.5, pp.1-15, 2014. 10.3389\/fphy.2014.00005","DOI":"10.3389\/fphy.2014.00005"},{"key":"32","doi-asserted-by":"crossref","unstructured":"[33] S. Kawakami, Y. Mukasa, S. Bao, D. Ba, J. Arai, S. Yagi, J. Teramoto, and N. Togawa, \u201cIsing-machine-based solver for constrained graph coloring problems,\u201d Proc. IEEE 41st International Conference on Consumer Electronics, 2023.","DOI":"10.1587\/transfun.2023KEP0003"},{"key":"33","unstructured":"[34] D. Marx, \u201cGraph colouring problems and their applications in scheduling,\u201d Periodica Polytechnica Electrical Engineering (Archives), vol.48, no.1-2, pp.11-16, 2004."},{"key":"34","doi-asserted-by":"publisher","unstructured":"[35] V. Maan and G. Purohit, \u201cA distributed approach for frequency allocation using graph coloring in mobile networks,\u201d International Journal of Computer Applications, vol.58, no.6, pp.9-13, 2012. 10.5120\/9284-3476","DOI":"10.5120\/9284-3476"},{"key":"35","unstructured":"[36] I.G. Rosenberg, \u201cReduction of bivalent maximization to the quadratic case,\u201d Cahiers du Centred'Etudes de Recherche Operationnelle, vol.17, pp.71-74, 1975."},{"key":"36","doi-asserted-by":"crossref","unstructured":"[37] V. Kolmogorov and R. Zabin, \u201cWhat energy functions can be minimized via graph cuts?,\u201d IEEE Trans. Pattern Anal. Mach. Intell., vol.26, no.2, pp.147-159, 2004. 10.1109\/tpami.2004.1262177","DOI":"10.1109\/TPAMI.2004.1262177"},{"key":"37","doi-asserted-by":"crossref","unstructured":"[38] D. Freedman and P. Drineas, \u201cEnergy minimization via graph cuts: Settling what is possible,\u201d 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), vol.2, pp.939-946, 2005. 10.1109\/cvpr.2005.143","DOI":"10.1109\/CVPR.2005.143"},{"key":"38","doi-asserted-by":"publisher","unstructured":"[39] D.J. Welsh and M.B. Powell, \u201cAn upper bound for the chromatic number of a graph and its application to timetabling problems,\u201d The Computer Journal, vol.10, no.1, pp.85-86, 1967. 10.1093\/comjnl\/10.1.85","DOI":"10.1093\/comjnl\/10.1.85"},{"key":"39","doi-asserted-by":"publisher","unstructured":"[40] 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 Operations Research, vol.39, no.3, pp.378-406, 1991. 10.1287\/opre.39.3.378","DOI":"10.1287\/opre.39.3.378"},{"key":"40","doi-asserted-by":"publisher","unstructured":"[41] R.L. Brooks, \u201cOn colouring the nodes of a network,\u201d Mathematical Proceedings of the Cambridge Philosophical Society, vol.37. no.2, pp.194-197, 1941. 10.1017\/s030500410002168x","DOI":"10.1017\/S030500410002168X"}],"container-title":["IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E107.A\/1\/E107.A_2023KEP0003\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,27]],"date-time":"2024-10-27T22:48:40Z","timestamp":1730069320000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E107.A\/1\/E107.A_2023KEP0003\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,1]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024]]}},"URL":"https:\/\/doi.org\/10.1587\/transfun.2023kep0003","relation":{},"ISSN":["0916-8508","1745-1337"],"issn-type":[{"value":"0916-8508","type":"print"},{"value":"1745-1337","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,1]]},"article-number":"2023KEP0003"}}