{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T23:22:57Z","timestamp":1743031377972,"version":"3.40.3"},"publisher-location":"Cham","reference-count":35,"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_22","type":"book-chapter","created":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T10:32:32Z","timestamp":1558348352000},"page":"337-354","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Optimality Clue for Graph Coloring Problem"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0116-021X","authenticated-orcid":false,"given":"Alexandre","family":"Gondran","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3749-3227","authenticated-orcid":false,"given":"Laurent","family":"Moalic","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,4,28]]},"reference":[{"issue":"5","key":"22_CR1","first-page":"1","volume":"19","author":"S Baillargeon","year":"2007","unstructured":"Baillargeon, S., Rivest, L.P.: Rcapture: loglinear models for capture-recapture in R. J. Stat. Softw. Art. 19(5), 1\u201331 (2007)","journal-title":"J. Stat. Softw. Art."},{"key":"22_CR2","doi-asserted-by":"publisher","unstructured":"Bollob\u00e1s, B.: Random Graphs. Cambridge Studies in Advanced Mathematics, 2 edn. Cambridge University Press (2001). \n                    https:\/\/doi.org\/10.1017\/CBO9780511814068","DOI":"10.1017\/CBO9780511814068"},{"issue":"4","key":"22_CR3","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":"9","key":"22_CR4","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1145\/362342.362367","volume":"16","author":"C Bron","year":"1973","unstructured":"Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16(9), 575\u2013577 (1973). \n                    https:\/\/doi.org\/10.1145\/362342.362367","journal-title":"Commun. ACM"},{"issue":"6","key":"22_CR5","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/0167-6377(90)90057-C","volume":"9","author":"R Carraghan","year":"1990","unstructured":"Carraghan, R., Pardalos, P.M.: An exact algorithm for the maximum clique problem. Oper. Res. Lett. 9(6), 375\u2013382 (1990). \n                    https:\/\/doi.org\/10.1016\/0167-6377(90)90057-C","journal-title":"Oper. Res. Lett."},{"key":"22_CR6","unstructured":"Ermon, S., Gomes, C.P., Selman, B.: Uniform solution sampling using a constraint solver as an oracle. In: de Freitas, N., Murphy, K.P. (eds.) Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence, Catalina Island, CA, USA, 14\u201318 August 2012, pp. 255\u2013264. AUAI Press (2012)"},{"key":"22_CR7","first-page":"4","volume":"2","author":"A Favier","year":"2011","unstructured":"Favier, A., de Givry, S., J\u00e9gou, P.: Solution counting for CSP and SAT with large tree-width. Control Syst. Comput. 2, 4\u201313 (2011)","journal-title":"Control Syst. Comput."},{"key":"22_CR8","doi-asserted-by":"publisher","unstructured":"Frieze, A., Vigoda, E.: A survey on the use of Markov chains to randomly sample colourings. Oxford University Press, Oxford (2007). Chap. 4. \n                    https:\/\/doi.org\/10.1093\/acprof:oso\/9780198571278.003.0004","DOI":"10.1093\/acprof:oso\/9780198571278.003.0004"},{"issue":"1","key":"22_CR9","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1002\/net.21716","volume":"69","author":"F Furini","year":"2017","unstructured":"Furini, F., Gabrel, V., Ternier, I.: An improved DSATUR-based branch-and-bound algorithm for the vertex coloring problem. Networks 69(1), 124\u2013141 (2017). \n                    https:\/\/doi.org\/10.1002\/net.21716","journal-title":"Networks"},{"issue":"4","key":"22_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. J. Comb. Optim. 3(4), 379\u2013397 (1999). \n                    https:\/\/doi.org\/10.1023\/A:1009823419804","journal-title":"J. Comb. Optim."},{"key":"22_CR11","unstructured":"Gomes, C.P., Hoffmann, J., Sabharwal, A., Selman, B.: From sampling to model counting. In: IJCA Proceedings IJCAI 2007, pp. 2293\u20132299. IJCAI (2007)"},{"key":"22_CR12","doi-asserted-by":"publisher","unstructured":"Gomes, C.P., Sabharwal, A., Selman, B.: Model counting. In: Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.) Handbook of Satisfiability, Frontiers in Artificial Intelligence and Applications, vol. 185, pp. 633\u2013654. IOS Press (2009). \n                    https:\/\/doi.org\/10.3233\/978-1-58603-929-5-633","DOI":"10.3233\/978-1-58603-929-5-633"},{"key":"22_CR13","doi-asserted-by":"publisher","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Polynomial algorithms for perfect graphs. In: Berge, C., Chv\u00e1tal, V. (eds.) Topics on Perfect Graphs, North-Holland Mathematics Studies, vol. 88, pp. 325\u2013356. North-Holland (1984). \n                    https:\/\/doi.org\/10.1016\/S0304-0208(08)72943-8","DOI":"10.1016\/S0304-0208(08)72943-8"},{"issue":"3","key":"22_CR14","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0020-0190(01)00263-0","volume":"82","author":"D Gusfield","year":"2002","unstructured":"Gusfield, D.: Partition-distance: a problem and class of perfect graphs arising in clustering. Inform. Process. Lett. 82(3), 159\u2013164 (2002)","journal-title":"Inform. Process. Lett."},{"issue":"4","key":"22_CR15","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/s12532-012-0042-3","volume":"4","author":"S Held","year":"2012","unstructured":"Held, S., Cook, W., Sewell, E.: Maximum-weight stable sets and safe lower bounds for graph coloring. Math. Program. Comput. 4(4), 363\u2013381 (2012). \n                    https:\/\/doi.org\/10.1007\/s12532-012-0042-3","journal-title":"Math. Program. Comput."},{"issue":"2","key":"22_CR16","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1002\/rsa.3240070205","volume":"7","author":"M Jerrum","year":"1995","unstructured":"Jerrum, M.: A very simple algorithm for estimating the number of k-colorings of a low-degree graph. Random Struct. Algorithms 7(2), 157\u2013165 (1995). \n                    https:\/\/doi.org\/10.1002\/rsa.3240070205","journal-title":"Random Struct. Algorithms"},{"key":"22_CR17","unstructured":"Jerrum, M.: Counting constraint satisfaction problems. In: Krokhin, A., Zivny, S. (eds.) The Constraint Satisfaction Problem: Complexity and Approximability, Dagstuhl Follow-Ups, vol. 7, pp. 205\u2013231. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2017)"},{"volume-title":"Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 1993, DIMACS Series in Discrete Mathematics and Theoretical Computer Science","year":"1996","key":"22_CR18","unstructured":"Johnson, D.S., Trick, M. (eds.): Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 1993, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26. American Mathematical Society, Providence (1996)"},{"key":"22_CR19","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R Karp","year":"1972","unstructured":"Karp, R.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"22_CR20","volume-title":"Ecology","author":"CJ Krebs","year":"2009","unstructured":"Krebs, C.J.: Ecology, 6th edn. Pearson, London (2009)","edition":"6"},{"key":"22_CR21","doi-asserted-by":"publisher","unstructured":"Li, C., Fang, Z., Xu, K.: Combining MaxSAT reasoning and incremental upper bound for the maximum clique problem. In: 2013 IEEE 25th International Conference on Tools with Artificial Intelligence, pp. 939\u2013946, November 2013. \n                    https:\/\/doi.org\/10.1109\/ICTAI.2013.143","DOI":"10.1109\/ICTAI.2013.143"},{"key":"22_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1111\/j.1475-3995.2009.00696.x","volume":"17","author":"E Malaguti","year":"2009","unstructured":"Malaguti, E., Toth, P.: A survey on vertex coloring problems. Int. Trans. Oper. Res. 17, 1\u201334 (2009)","journal-title":"Int. Trans. Oper. Res."},{"issue":"1","key":"22_CR23","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10852-012-9177-5","volume":"12","author":"M\u00c9 Marmion","year":"2013","unstructured":"Marmion, M.\u00c9., Jourdan, L., Dhaenens, C.: Fitness landscape analysis and metaheuristics efficiency. J. Math. Model. Algorithms Oper. Res. 12(1), 3\u201326 (2013). \n                    https:\/\/doi.org\/10.1007\/s10852-012-9177-5","journal-title":"J. Math. Model. Algorithms Oper. Res."},{"key":"22_CR24","unstructured":"Merz, P.: Memetic algorithms for combinatorial optimization problems: fitness landscapes and effective search strategies. Ph.D. thesis, Department of Electrical Engineering and Computer Science, University of Siegen, Germany (2000)"},{"issue":"Suppl. C","key":"22_CR25","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/j.dam.2015.05.003","volume":"210","author":"S Miracle","year":"2016","unstructured":"Miracle, S., Randall, D.: Algorithms to approximately count and sample conforming colorings of graphs. Discret. Appl. Math. 210(Suppl. C), 133\u2013149 (2016). lAGOS 2013: Seventh Latin-American Algorithms, Graphs, and Optimization Symposium, Playa del Carmen, M\u00e9xico \u2013 2013","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"22_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10732-017-9354-9","volume":"24","author":"L Moalic","year":"2018","unstructured":"Moalic, L., Gondran, A.: Variations on memetic algorithms for graph. J. Heuristics 24(1), 1\u201324 (2018). \n                    https:\/\/doi.org\/10.1007\/s10732-017-9354-9","journal-title":"J. Heuristics"},{"issue":"2","key":"22_CR27","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1137\/0602012","volume":"2","author":"J Orlin","year":"1981","unstructured":"Orlin, J., Bonuccelli, M., Bovet, D.: An \n                    \n                      \n                    \n                    $$O(n^2)$$\n                   algorithm for coloring proper circular arc graphs. SIAM J. Algebraic Discret. Methods 2(2), 88\u201393 (1981). \n                    https:\/\/doi.org\/10.1137\/0602012","journal-title":"SIAM J. Algebraic Discret. Methods"},{"issue":"1","key":"22_CR28","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/S0166-218X(01)00290-6","volume":"120","author":"PR \u00d6sterg\u00e5rd","year":"2002","unstructured":"\u00d6sterg\u00e5rd, P.R.: A fast algorithm for the maximum clique problem. Discret. Appl. Math. 120(1), 197\u2013207 (2002). \n                    https:\/\/doi.org\/10.1016\/S0166-218X(01)00290-6\n                    \n                  . Special Issue devoted to the 6th Twente Workshop on Graphs and Combinatorial Optimization","journal-title":"Discret. Appl. Math."},{"issue":"6","key":"22_CR29","doi-asserted-by":"publisher","first-page":"1575","DOI":"10.11650\/twjm\/1500404576","volume":"10","author":"ASP Pedersen","year":"2006","unstructured":"Pedersen, A.S.P., Vestergaard, P.D.: Bounds on the number of vertex independent sets in a graph. Taiwan. J. Math. 10(6), 1575\u20131587 (2006)","journal-title":"Taiwan. J. Math."},{"key":"22_CR30","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/j.ejc.2015.02.005","volume":"48","author":"W Samotij","year":"2015","unstructured":"Samotij, W.: Counting independent sets in graphs. Eur. J. Comb. 48, 5\u201318 (2015). \n                    https:\/\/doi.org\/10.1016\/j.ejc.2015.02.005","journal-title":"Eur. J. Comb."},{"issue":"3","key":"22_CR31","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/0166-218X(89)90011-5","volume":"25","author":"WK Shih","year":"1989","unstructured":"Shih, W.K., Hsu, W.L.: An \n                    \n                      \n                    \n                    $$O(n^{1.5})$$\n                   algorithm to color proper circular arcs. Discret. Appl. Math. 25(3), 321\u2013323 (1989). \n                    https:\/\/doi.org\/10.1016\/0166-218X(89)90011-5","journal-title":"Discret. Appl. Math."},{"issue":"11","key":"22_CR32","doi-asserted-by":"publisher","first-page":"e50060","DOI":"10.1371\/journal.pone.0050060","volume":"7","author":"O Titiloye","year":"2012","unstructured":"Titiloye, O., Crispin, A.: Parameter tuning patterns for random graph coloring with quantum annealing. PLoS ONE 7(11), e50060 (2012). \n                    https:\/\/doi.org\/10.1371\/journal.pone.0050060","journal-title":"PLoS ONE"},{"issue":"3","key":"22_CR33","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410\u2013421 (1979). \n                    https:\/\/doi.org\/10.1137\/0208032","journal-title":"SIAM J. Comput."},{"key":"22_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/11499107_24","volume-title":"Theory and Applications of Satisfiability Testing","author":"W Wei","year":"2005","unstructured":"Wei, W., Selman, B.: A new approach to model counting. In: Bacchus, F., Walsh, T. (eds.) SAT 2005. LNCS, vol. 3569, pp. 324\u2013339. Springer, Heidelberg (2005). \n                    https:\/\/doi.org\/10.1007\/11499107_24"},{"issue":"6","key":"22_CR35","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(6), 103\u2013128 (2007). \n                    https:\/\/doi.org\/10.4086\/toc.2007.v003a006\n                    \n                  . \n                    http:\/\/www.theoryofcomputing.org\/articles\/v003a006","journal-title":"Theory Comput."}],"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_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T19:10:55Z","timestamp":1558984255000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-19212-9_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030192112","9783030192129"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-19212-9_22","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"}}]}}