{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T15:43:36Z","timestamp":1725637416415},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642258695"},{"type":"electronic","value":"9783642258701"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-25870-1_17","type":"book-chapter","created":{"date-parts":[[2011,11,30]],"date-time":"2011-11-30T13:32:45Z","timestamp":1322659965000},"page":"179-190","source":"Crossref","is-referenced-by-count":2,"title":["Empires Make Cartography Hard: The Complexity of the Empire Colouring Problem"],"prefix":"10.1007","author":[{"given":"Andrew R. A.","family":"McGrae","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michele","family":"Zito","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"11","key":"17_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0898-1221(97)00214-9","volume":"34","author":"L.W. Beineke","year":"1997","unstructured":"Beineke, L.W.: Biplanar graphs: a survey. Computers and Mathematical Applications\u00a034(11), 1\u20138 (1997)","journal-title":"Computers and Mathematical Applications"},{"key":"17_CR2","doi-asserted-by":"publisher","first-page":"850","DOI":"10.4153\/CJM-1965-084-2","volume":"17","author":"L.W. Beineke","year":"1965","unstructured":"Beineke, L.W., Harary, F.: The thickness of the complete graph. Canadian Journal of Mathematics\u00a017, 850\u2013859 (1965)","journal-title":"Canadian Journal of Mathematics"},{"key":"17_CR3","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1017\/S030500410002168X","volume":"37","author":"R.L. Brooks","year":"1941","unstructured":"Brooks, R.L.: On colouring the nodes of a network. Proc. Cambridge Phil. Soc.\u00a037, 194\u2013197 (1941)","journal-title":"Proc. Cambridge Phil. Soc."},{"key":"17_CR4","doi-asserted-by":"crossref","unstructured":"Bryant, D.E.: Cycle decompositions of the complete graphs. In: Hilton, A.J.W., Talbot, J.M. (eds.) Surveys in Combinatorics. London Mathematical Society Lecture Notes Series, vol.\u00a0346, pp. 67\u201397. Cambridge University Press (2007)","DOI":"10.1017\/CBO9780511666209.004"},{"key":"17_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1007\/978-3-642-03409-1_8","volume-title":"Fundamentals of Computation Theory","author":"C. Cooper","year":"2009","unstructured":"Cooper, C., McGrae, A.R.A., Zito, M.: Martingales on Trees and the Empire Chromatic Number of Random Trees. In: Kuty\u0142owski, M., Gebala, M., Charatonik, W. (eds.) FCT 2009. LNCS, vol.\u00a05699, pp. 74\u201383. Springer, Heidelberg (2009)"},{"key":"17_CR6","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. M.I.T. Press (2009)"},{"key":"17_CR7","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory","author":"R. Diestel","year":"1999","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol.\u00a0173. Springer, Heidelberg (1999)"},{"key":"17_CR8","unstructured":"Garey, M.R., Johnson, D.S.: Computer and Intractability, a Guide to the Theory of NP-Completeness. Freeman and Company (1979)"},{"key":"17_CR9","unstructured":"Gibbons, A.M.: Algorithmic Graph Theory. Cambridge University Press (1985)"},{"key":"17_CR10","first-page":"332","volume":"24","author":"P.J. Heawood","year":"1890","unstructured":"Heawood, P.J.: Map colour theorem. Quarterly Journal of Pure and Applied Mathematics\u00a024, 332\u2013338 (1890)","journal-title":"Quarterly Journal of Pure and Applied Mathematics"},{"issue":"4","key":"17_CR11","doi-asserted-by":"publisher","first-page":"211","DOI":"10.2307\/2690733","volume":"66","author":"J.P. Hutchinson","year":"1993","unstructured":"Hutchinson, J.P.: Coloring ordinary maps, maps of empires, and maps of the moon. Mathematics Magazine\u00a066(4), 211\u2013226 (1993)","journal-title":"Mathematics Magazine"},{"key":"17_CR12","first-page":"146","volume":"347","author":"B. Jackson","year":"1983","unstructured":"Jackson, B., Ringel, G.: Solution of Heawood\u2019s empire problem in the plane. Journal f\u00fcr die Reine und Angewandte Mathematik\u00a0347, 146\u2013153 (1983)","journal-title":"Journal f\u00fcr die Reine und Angewandte Mathematik"},{"key":"17_CR13","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: 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":"17_CR14","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L.: Combinatorial Problems and Exercises, 2nd edn. North-Holland (1993)","DOI":"10.1016\/B978-0-444-81504-0.50006-0"},{"key":"17_CR15","unstructured":"Lucas, E.: R\u00e9creations Math\u00e9matiqu\u00e9s, vol.\u00a0II. Gauthier-Villars (1892)"},{"key":"17_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/978-3-540-85238-4_42","volume-title":"Mathematical Foundations of Computer Science 2008","author":"A.R. McGrae","year":"2008","unstructured":"McGrae, A.R., Zito, M.: Colouring Random Empire Trees. In: Ochma\u0144ski, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol.\u00a05162, pp. 515\u2013526. Springer, Heidelberg (2008)"},{"key":"17_CR17","unstructured":"McGrae, A.R.A.: Colouring Empires in Random Trees. PhD thesis, Department of Computer Science, University of Liverpool as technical report ULCS-10-007 (2010), http:\/\/www.csc.liv.ac.uk\/research\/techreports\/techreports.html"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-25870-1_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T04:04:44Z","timestamp":1561003484000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-25870-1_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642258695","9783642258701"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-25870-1_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}