{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:53:05Z","timestamp":1725493985149},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540671596"},{"type":"electronic","value":"9783540465218"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-46521-9_9","type":"book-chapter","created":{"date-parts":[[2007,11,3]],"date-time":"2007-11-03T18:47:16Z","timestamp":1194115636000},"page":"102-112","source":"Crossref","is-referenced-by-count":1,"title":["The Hardness of Placing Street Names in a Manhattan Type Map"],"prefix":"10.1007","author":[{"given":"Sebastian","family":"Seibert","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Walter","family":"Unger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2000,2,14]]},"reference":[{"key":"9_CR1","unstructured":"Jon Christensen, Joe Marks, Stuart Shieber: Labeling Point Features on Maps and Diagrams, Harvard CS, 1992, TR-25-92."},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Michael Formann, Frank Wagner: A Packing Problem with Applications to Lettering of Maps, Proc. 7th Annu. ACM Sympos. Comput. Geom., 1991, pp. 281\u2013288.","DOI":"10.1145\/109648.109680"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad: Some optimal inapproximability results, in Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997, pp. 1\u201310.","DOI":"10.1145\/258533.258536"},{"key":"9_CR4","unstructured":"D. S. Hochbaum (Ed.): Approximation Algorithms for NP-hard Problems. PWS Publishing Company 1996."},{"key":"9_CR5","volume-title":"NP-Hardness of Some Map Labeling Problems","author":"C. Iturriaga","year":"1997","unstructured":"Claudia Iturriaga, Anna Lubiw: NP-Hardness of Some Map Labeling Problems, University of Waterloo, Canada, 1997, CS-97-18."},{"key":"9_CR6","unstructured":"T. Kato, H. Imai: The NP-Completeness of the Character Placement Problem of 2 or 3 degrees of freedom, Record of Joint Conference of Electrical and Electronic Engineers in Kyushu, 1988, pp. 1138."},{"issue":"3","key":"9_CR7","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1137\/0405033","volume":"5","author":"D. E. Knuth","year":"1992","unstructured":"Donald E. Knuth, Arvind Raghunathan: The Problem of Compatible Representatives, SIAM J. Discr. Math., 1992, Vol. 5, Nr. 3, pp. 422\u2013427.","journal-title":"SIAM J. Discr. Math."},{"key":"9_CR8","series-title":"Lect Notes Comput Sci","volume-title":"Lectures on Proof Verification and Approximation Algorithms","year":"1998","unstructured":"E. W. Mayr, H. J. Pr\u00f6mel, A. Steger (Eds.): Lectures on Proof Verification and Approximation Algorithms. LNCS 1967, Springer 1998."},{"key":"9_CR9","unstructured":"Joe Marks, Stuart Shieber: The Computational Complexity of Cartographic Label Placement, Harvard CS, 1991, TR-05-91."},{"key":"9_CR10","volume-title":"Labeling Downtown","author":"G. Neyer","year":"1999","unstructured":"Gabriele Neyer, Frank Wagner: Labeling Downtown, Department of Computer Science, ETH Zurich, Switzerland, TR 324, May 1999"},{"key":"9_CR11","unstructured":"Tycho Strijk, Alexander Wolff: Labeling Points with Circles, Institut f\u00fcr Informatik, Freie Universit\u00e4t Berlin, 1999, B 99-08."},{"key":"9_CR12","unstructured":"Tycho Strijk, Alexander Wolff: The Map Labeling Bibliography, http:\/\/www.inf.fu-berlin.de\/map-labeling\/bibliography ."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46521-9_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T00:44:40Z","timestamp":1556930680000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46521-9_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671596","9783540465218"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-46521-9_9","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}