{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T09:40:02Z","timestamp":1766137202317,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030192112"},{"type":"electronic","value":"9783030192129"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-19212-9_25","type":"book-chapter","created":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T10:32:32Z","timestamp":1558348352000},"page":"374-390","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["A Hybrid Approach for Exact Coloring of Massive Graphs"],"prefix":"10.1007","author":[{"given":"Emmanuel","family":"Hebrard","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"George","family":"Katsirelos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,4,28]]},"reference":[{"issue":"1","key":"25_CR1","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s10479-007-0178-0","volume":"153","author":"KI Aardal","year":"2007","unstructured":"Aardal, K.I., Hoesel, S.P.M.V., Koster, A.M.C.A., Mannino, C., Sassano, A.: Models and solution techniques for frequency assignment problems. Ann. Oper. Res. 153(1), 79\u2013129 (2007)","journal-title":"Ann. Oper. Res."},{"key":"25_CR2","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1090\/dimacs\/050\/06","volume-title":"External Memory Algorithms","author":"J Abello","year":"1999","unstructured":"Abello, J., Pardalos, P., Resende, M.G.C.: On maximum clique problems in very large graphs. In: Abello, J.M., Vitter, J.S. (eds.) External Memory Algorithms, pp. 119\u2013130. American Mathematical Society, Boston (1999)"},{"unstructured":"Bader, D.A., Meyerhenke, H., Sanders, P., Wagner, D.: Graph partitioning and graph clustering (2012). \n                    http:\/\/www.cc.gatech.edu\/dimacs10\/","key":"25_CR3"},{"issue":"3","key":"25_CR4","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. Comput. Oper. Res. 35(3), 960\u2013975 (2008)","journal-title":"Comput. Oper. Res."},{"issue":"4","key":"25_CR5","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1145\/359094.359101","volume":"22","author":"D Br\u00e9laz","year":"1979","unstructured":"Br\u00e9laz, D.: New methods to color the vertices of a graph. Commun. ACM 22(4), 251\u2013256 (1979)","journal-title":"Commun. ACM"},{"issue":"1","key":"25_CR6","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0096-0551(81)90048-5","volume":"6","author":"GJ Chaitin","year":"1981","unstructured":"Chaitin, G.J., Auslander, M.A., Chandra, A.K., Cocke, J., Hopkins, M.E., Markstein, P.W.: Register allocation via coloring. Comput. Lang. 6(1), 47\u201357 (1981)","journal-title":"Comput. Lang."},{"issue":"6","key":"25_CR7","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1016\/j.orl.2008.08.002","volume":"36","author":"D Cornaz","year":"2008","unstructured":"Cornaz, D., Jost, V.: A one-to-one correspondence between colorings and stable sets. Oper. Res. Lett. 36(6), 673\u2013676 (2008)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"25_CR8","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0377-2217(85)90167-5","volume":"19","author":"D Werra de","year":"1985","unstructured":"de Werra, D.: An introduction to timetabling. Eur. J. Oper. Res. 19(2), 151\u2013162 (1985)","journal-title":"Eur. J. Oper. Res."},{"key":"25_CR9","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.endm.2016.03.020","volume":"52","author":"F Furini","year":"2016","unstructured":"Furini, F., Gabrel, V., Ternier, I.-C.: Lower bounding techniques for DSATUR-based branch and bound. Electron. Notes Discrete Math. 52, 149\u2013156 (2016). INOC 2015\u20137th International Network Optimization Conference","journal-title":"Electron. Notes Discrete Math."},{"issue":"16\u201317","key":"25_CR10","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., Qinghua, W.: Improving the extraction and expansion method for large graph coloring. Discrete Appl. Math. 160(16\u201317), 2397\u20132407 (2012)","journal-title":"Discrete Appl. Math."},{"key":"25_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/978-3-319-98334-9_12","volume-title":"Principles and Practice of Constraint Programming","author":"E Hebrard","year":"2018","unstructured":"Hebrard, E., Katsirelos, G.: Clause learning and new bounds for graph coloring. In: Hooker, J. (ed.) CP 2018. LNCS, vol. 11008, pp. 179\u2013194. Springer, Cham (2018). \n                    https:\/\/doi.org\/10.1007\/978-3-319-98334-9_12"},{"issue":"4","key":"25_CR12","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 39(4), 345\u2013351 (1987)","journal-title":"Computing"},{"volume-title":"Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11\u201313, 1993","year":"1996","unstructured":"Johnson, D.J., Trick, M.A. (eds.): Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11\u201313, 1993. American Mathematical Society, Boston (1996)","key":"25_CR13"},{"key":"25_CR14","doi-asserted-by":"publisher","first-page":"489","DOI":"10.6028\/jres.084.024","volume":"84","author":"FT Leighton","year":"1979","unstructured":"Leighton, F.T.: A graph coloring algorithm for large scheduling problems. J. Res. Natl. Bur. Stand. 84, 489\u2013506 (1979)","journal-title":"J. Res. Natl. Bur. Stand."},{"unstructured":"Leskovec, J., Krevl, A.: SNAP datasets: Stanford large network dataset collection (2014). \n                    http:\/\/snap.stanford.edu\/data","key":"25_CR15"},{"doi-asserted-by":"crossref","unstructured":"Lin, J., Cai, S., Luo, C., Su, K.: A reduction based method for coloring very large graphs. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, pp. 517\u2013523 (2017)","key":"25_CR16","DOI":"10.24963\/ijcai.2017\/73"},{"issue":"1","key":"25_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L Lov\u00e1sz","year":"2006","unstructured":"Lov\u00e1sz, L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theor. 25(1), 1\u20137 (2006)","journal-title":"IEEE Trans. Inf. Theor."},{"issue":"2","key":"25_CR18","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.: An exact approach for the vertex coloring problem. Discrete Optim. 8(2), 174\u2013190 (2011)","journal-title":"Discrete Optim."},{"issue":"3","key":"25_CR19","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1145\/2402.322385","volume":"30","author":"DW Matula","year":"1983","unstructured":"Matula, D.W., Beck, L.L.: Smallest-last ordering and clustering and graph coloring algorithms. J. ACM 30(3), 417\u2013427 (1983)","journal-title":"J. ACM"},{"key":"25_CR20","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1287\/ijoc.8.4.344","volume":"8","author":"A Mehrotra","year":"1995","unstructured":"Mehrotra, A., Trick, M.A.: A column generation approach for graph coloring. INFORMS J. Comput. 8, 344\u2013354 (1995)","journal-title":"INFORMS J. Comput."},{"unstructured":"Moalic, L., Gondran, A.: Variations on memetic algorithms for graph coloring problems. CoRR, abs\/1401.2184 (2014)","key":"25_CR21"},{"key":"25_CR22","doi-asserted-by":"publisher","first-page":"161","DOI":"10.4064\/cm-3-2-161-162","volume":"3","author":"J Mycielski","year":"1955","unstructured":"Mycielski, J.: Sur le coloriage des graphes. Colloq. Math. 3, 161\u2013162 (1955)","journal-title":"Colloq. Math."},{"issue":"2","key":"25_CR23","doi-asserted-by":"publisher","first-page":"258","DOI":"10.15807\/jorsj.39.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. J. Oper. Res. Soc. Jpn. 39(2), 258\u2013265 (1996)","journal-title":"J. Oper. Res. Soc. Jpn."},{"doi-asserted-by":"crossref","unstructured":"Rossi, R.A., Ahmed, N.K.: Coloring large complex networks. CoRR, abs\/1403.3448 (2014)","key":"25_CR24","DOI":"10.1007\/s13278-014-0228-y"},{"key":"25_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/978-3-642-02777-2_22","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2009","author":"B Schaafsma","year":"2009","unstructured":"Schaafsma, B., Heule, M.J.H., van Maaren, H.: Dynamic symmetry breaking by simulating zykov contraction. In: Kullmann, O. (ed.) SAT 2009. LNCS, vol. 5584, pp. 223\u2013236. Springer, Heidelberg (2009). \n                    https:\/\/doi.org\/10.1007\/978-3-642-02777-2_22"},{"issue":"7","key":"25_CR26","doi-asserted-by":"publisher","first-page":"1724","DOI":"10.1016\/j.cor.2011.10.008","volume":"39","author":"PS Segundo","year":"2012","unstructured":"Segundo, P.S.: A new DSATUR-based algorithm for exact vertex coloring. Comput. Oper. Res. 39(7), 1724\u20131733 (2012)","journal-title":"Comput. Oper. Res."},{"issue":"2","key":"25_CR27","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1016\/j.dam.2006.07.016","volume":"156","author":"A Gelder Van","year":"2008","unstructured":"Van Gelder, A.: Another look at graph coloring via propositional satisfiability. Discrete Appl. Math. 156(2), 230\u2013243 (2008)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"25_CR28","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.: Solving the maximum clique and vertex coloring problems on very large sparse networks. INFORMS J. Comput. 27(1), 164\u2013177 (2015)","journal-title":"INFORMS J. Comput."},{"unstructured":"Walteros, J.L., Buchanan, A.: Why is maximum clique often easy in practice? Optimization Online (2018). \n                    http:\/\/www.optimization-online.org\/DB_HTML\/2018\/07\/6710.html","key":"25_CR29"},{"key":"25_CR30","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1016\/j.cor.2014.05.017","volume":"51","author":"Z Zhou","year":"2014","unstructured":"Zhou, Z., Li, C.-M., Huang, C., Ruchu, X.: An exact algorithm with learning for the graph coloring problem. Comput. Oper. Res. 51, 282\u2013301 (2014)","journal-title":"Comput. Oper. Res."}],"container-title":["Lecture Notes in Computer Science","Integration of Constraint Programming, Artificial Intelligence, and Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-19212-9_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T19:10:37Z","timestamp":1558984237000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-19212-9_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030192112","9783030192129"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-19212-9_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"28 April 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CPAIOR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Thessaloniki","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 June 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 June 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cpaior2019b","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cpaior2019.uowm.gr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"94","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"34","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"9","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"36% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"5.67","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}}]}}