{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T16:29:31Z","timestamp":1710347371132},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,8,16]],"date-time":"2012-08-16T00:00:00Z","timestamp":1345075200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,2]]},"DOI":"10.1007\/s00453-012-9680-0","type":"journal-article","created":{"date-parts":[[2012,8,15]],"date-time":"2012-08-15T16:45:40Z","timestamp":1345049140000},"page":"483-503","source":"Crossref","is-referenced-by-count":3,"title":["The Complexity of the Empire Colouring Problem"],"prefix":"10.1007","volume":"68","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","published-online":{"date-parts":[[2012,8,16]]},"reference":[{"issue":"11","key":"9680_CR1","doi-asserted-by":"crossref","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\u00a0survey. Comput. Math. Appl. 34(11), 1\u20138 (1997)","journal-title":"Comput. Math. Appl."},{"key":"9680_CR2","doi-asserted-by":"crossref","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. Can. J. Math. 17, 850\u2013859 (1965)","journal-title":"Can. J. Math."},{"issue":"1","key":"9680_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1017\/S0305004100037385","volume":"60","author":"L.W. Beineke","year":"1964","unstructured":"Beineke, L.W., Harary, F., Moon, J.W.: On the thickness of the complete bipartite graph. Proc. Camb. Philos. Soc. 60(1), 1\u20135 (1964)","journal-title":"Proc. Camb. Philos. Soc."},{"key":"9680_CR4","doi-asserted-by":"crossref","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. Camb. Philos. Soc. 37, 194\u2013197 (1941)","journal-title":"Proc. Camb. Philos. Soc."},{"key":"9680_CR5","series-title":"London Mathematical Society Lecture Notes Series","first-page":"67","volume-title":"Surveys in Combinatorics","author":"D.E. Bryant","year":"2007","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, Cambridge (2007)"},{"key":"9680_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1007\/978-3-642-03409-1_8","volume-title":"FCT 2009","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. Lecture Notes in Computer Science, vol. 5699, pp. 74\u201383. Springer, Berlin (2009)"},{"key":"9680_CR7","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"key":"9680_CR8","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. 173. Springer, Berlin (1999)"},{"key":"9680_CR9","volume-title":"Computer and Intractability, a Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computer and Intractability, a Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"9680_CR10","volume-title":"Algorithmic Graph Theory","author":"A.M. Gibbons","year":"1985","unstructured":"Gibbons, A.M.: Algorithmic Graph Theory. Cambridge University Press, Cambridge (1985)"},{"key":"9680_CR11","first-page":"332","volume":"24","author":"P.J. Heawood","year":"1890","unstructured":"Heawood, P.J.: Map colour theorem. Q. J. Pure Appl. Math. 24, 332\u2013338 (1890)","journal-title":"Q. J. Pure Appl. Math."},{"issue":"4","key":"9680_CR12","doi-asserted-by":"crossref","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. Math. Mag. 66(4), 211\u2013226 (1993)","journal-title":"Math. Mag."},{"key":"9680_CR13","first-page":"146","volume":"347","author":"B. Jackson","year":"1983","unstructured":"Jackson, B., Ringel, G.: Solution of Heawood\u2019s empire problem in the plane. J. Reine Angew. Math. 347, 146\u2013153 (1983)","journal-title":"J. Reine Angew. Math."},{"key":"9680_CR14","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations. Proceedings of a Symposium on the 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. Proceedings of a Symposium on the Complexity of Computer Computations, March 1972, Yorktown Heights, NY, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"9680_CR15","volume-title":"Combinatorial Problems and Exercises","author":"L. Lov\u00e1sz","year":"1993","unstructured":"Lov\u00e1sz, L.: Combinatorial Problems and Exercises, 2nd edn. North-Holland, Amsterdam (1993)","edition":"2"},{"key":"9680_CR16","volume-title":"R\u00e9creations Math\u00e9matiqu\u00e9s","author":"E. Lucas","year":"1892","unstructured":"Lucas, E.: R\u00e9creations Math\u00e9matiqu\u00e9s, vol.\u00a0II. Gauthier-Villars, Paris (1892)"},{"key":"9680_CR17","volume-title":"D-NET PUBLICATIONS","author":"E. M\u00e4kinen","year":"2009","unstructured":"M\u00e4kinen, E., Poranen, T.: An annotated bibliography on the thickness, outerthickness, and arboricity of a graph. In: D-NET PUBLICATIONS, vol. D-2009-3. University of Tampere, Tampere (2009)"},{"key":"9680_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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.) Mathematical Foundations of Computer Science 2008. Lecture Notes in Computer Science, vol. 5162, pp. 515\u2013526. Springer, Berlin (2008)"},{"key":"9680_CR19","unstructured":"McGrae, A.R.A.: Colouring empires in random trees. PhD thesis, Department of Computer Science, University of Liverpool (2010). Available from http:\/\/www.csc.liv.ac.uk\/research\/techreports\/techreports.html as technical report ULCS-10-007"},{"key":"9680_CR20","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/PL00007219","volume":"14","author":"P. Mutzel","year":"1998","unstructured":"Mutzel, P., Odenthal, T., Scharbrodt, M.: The thickness of graphs: a\u00a0survey. Graphs Comb. 14, 59\u201373 (1998)","journal-title":"Graphs Comb."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9680-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9680-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9680-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:10Z","timestamp":1559137510000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9680-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,16]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["9680"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9680-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8,16]]}}}