{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T17:23:51Z","timestamp":1725470631185},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540397281"},{"type":"electronic","value":"9783540397304"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11856290_19","type":"book-chapter","created":{"date-parts":[[2006,9,19]],"date-time":"2006-09-19T07:36:09Z","timestamp":1158651369000},"page":"211-225","source":"Crossref","is-referenced-by-count":1,"title":["Using Haj\u00f3s\u2019 Construction to Generate Hard Graph 3-Colorability Instances"],"prefix":"10.1007","author":[{"given":"Sheng","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jian","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"19_CR1","volume-title":"Computers and Intractability - A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability - A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco (1979)"},{"issue":"4","key":"19_CR2","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1145\/3341.3350","volume":"28","author":"M. Kubale","year":"1985","unstructured":"Kubale, M., Jackowski, B.: A generalized implicit enumeration algorithm for graph coloring. Commun. ACM\u00a028(4), 412\u2013418 (1985)","journal-title":"Commun. ACM"},{"key":"19_CR3","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1287\/ijoc.8.4.344","volume":"8","author":"A. Mehrotra","year":"1996","unstructured":"Mehrotra, A., Trick, M.A.: A column generation approach for graph coloring. INFORMS Journal on Computing\u00a08, 344\u2013354 (1996)","journal-title":"INFORMS Journal on Computing"},{"volume-title":"Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop","year":"1996","key":"19_CR4","unstructured":"Johnson, D.S., Trick, M.A. (eds.): Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11-13, 1993. American Mathematical Society, Boston (1996)"},{"issue":"4","key":"19_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\u00a022(4), 251\u2013256 (1979)","journal-title":"Commun. ACM"},{"issue":"8","key":"19_CR6","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1145\/358161.358171","volume":"26","author":"J. Peem\u00f6ller","year":"1983","unstructured":"Peem\u00f6ller, J.: A correction to Br\u00e9laz\u2019s modification of Brown\u2019s coloring algorithm. Commun. ACM\u00a026(8), 595\u2013597 (1983)","journal-title":"Commun. ACM"},{"issue":"4","key":"19_CR7","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\u00a039(4), 345\u2013351 (1987)","journal-title":"Computing"},{"issue":"4","key":"19_CR8","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.\u00a03(4), 379\u2013397 (1999)","journal-title":"J. Comb. Optim."},{"key":"19_CR9","doi-asserted-by":"crossref","unstructured":"Vlasie, R.D.: Systematic generation of very hard cases for graph 3-colorability. In: Proceedings of 7th IEEE ICTAI (1995)","DOI":"10.1109\/TAI.1995.479412"},{"key":"19_CR10","unstructured":"Cheeseman, P., Kanefsky, B., Taylor, W.M.: Where the really hard problems are. In: Proceedings of the 12th IJCAI, pp. 331\u2013337 (1991)"},{"key":"19_CR11","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/0004-3702(94)90088-4","volume":"69","author":"T. Hogg","year":"1994","unstructured":"Hogg, T., Williams, C.P.: The hardest constraint problems: A double phase transition. Artificial Intelligence\u00a069, 359\u2013377 (1994)","journal-title":"Artificial Intelligence"},{"key":"19_CR12","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1613\/jair.370","volume":"7","author":"D.L. Mammen","year":"1997","unstructured":"Mammen, D.L., Hogg, T.: A new look at the easy-hard-easy pattern of combinatorial search difficulty. Journal of Artificial Intelligence Research\u00a07, 47\u201366 (1997)","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"1\u20132","key":"19_CR13","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/S0304-3975(01)00164-5","volume":"265","author":"J. Culberson","year":"2001","unstructured":"Culberson, J., Gent, I.: Frozen development in graph coloring. Theoretical Computer Science\u00a0265(1\u20132), 227\u2013264 (2001)","journal-title":"Theoretical Computer Science"},{"key":"19_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"914","DOI":"10.1007\/978-3-540-45193-8_78","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2003","author":"S. Nishihara","year":"2003","unstructured":"Nishihara, S., Mizuno, K., Nishihara, K.: A composition algorithm for very hard graph 3-colorability instances. In: Rossi, F. (ed.) CP 2003. LNCS, vol.\u00a02833, pp. 914\u2013919. Springer, Heidelberg (2003)"},{"key":"19_CR15","volume-title":"Constraint Processing","author":"R. Dechter","year":"2003","unstructured":"Dechter, R.: Constraint Processing. Morgan Kaufmann, San Francisco (2003)"},{"key":"19_CR16","volume-title":"Graph Coloring Problems","author":"T.R. Jensen","year":"1995","unstructured":"Jensen, T.R., Toft, B.: Graph Coloring Problems. Wiley, New York (1995)"},{"issue":"1","key":"19_CR17","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1023\/A:1013665718444","volume":"8","author":"M. Caramia","year":"2002","unstructured":"Caramia, M., Dell\u2019Olmo, P.: Constraint propagation in graph coloring. Journal of Heuristics\u00a08(1), 83\u2013107 (2002)","journal-title":"Journal of Heuristics"}],"container-title":["Lecture Notes in Computer Science","Artificial Intelligence and Symbolic Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11856290_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:20:00Z","timestamp":1619508000000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11856290_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540397281","9783540397304"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/11856290_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}