{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:02:07Z","timestamp":1725483727542},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540678236"},{"type":"electronic","value":"9783540449294"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44929-9_16","type":"book-chapter","created":{"date-parts":[[2007,5,5]],"date-time":"2007-05-05T13:20:53Z","timestamp":1178371253000},"page":"200-212","source":"Crossref","is-referenced-by-count":3,"title":["Maximum Clique and Minimum Clique Partition in Visibility Graphs"],"prefix":"10.1007","author":[{"given":"Stephan","family":"Eidenbenz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoph","family":"Stamm","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,8,24]]},"reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, S. Ghosh, and R. Shyamasundar; Computational Complexity of Restricted Polygon Decompositions; Computational Morphology, G. Toussaint, ed., North-Holland, pp. 1\u201311, 1988.","DOI":"10.1016\/B978-0-444-70467-2.50006-0"},{"key":"16_CR2","unstructured":"S. Arora and C. Lund; Hardness of Approximations; in: Approximation Algorithms for NP-Hard Problems (ed. Dorit Hochbaum), PWS Publishing Company, pp. 399\u2013446, 1996."},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"D. Avis and D. Rappaport; Computing the largest empty convex subset of a set of points; Proc. 1st Ann. ACM Symposium Computational Geometry, pp. 161\u2013167, 1985.","DOI":"10.1145\/323233.323255"},{"key":"16_CR4","volume-title":"Complexity and Approximation. Combinatorial Optimization Problems and their Approximability Properties","author":"P. Crescenzi","year":"1999","unstructured":"P. Crescenzi, V. Kann; A Compendium of NP Optimization Problems; in the book by G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Complexity and Approximation. Combinatorial Optimization Problems and their Approximability Properties, Springer-Verlag, Berlin, 1999; also available in an online-version at: http:\/\/www.nada.kth.se\/theory\/compendium\/ ."},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"J. C. Culberson and R. A. Reckhow; Covering Polygons is hard; Proc. 29th Symposium on Foundations of Computer Science, 1988.","DOI":"10.1109\/SFCS.1988.21976"},{"key":"16_CR6","first-page":"561","volume":"5","author":"D. P. Dobkin","year":"1990","unstructured":"David P. Dobkin, Herbert Edelsbrunner, and Mark H. Overmars; Searching for Empty Convex Polygons; Algorithmica, 5, pp. 561\u2013571, 1990.","journal-title":"Searching for Empty Convex Polygons"},{"key":"16_CR7","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0022-0000(89)90038-X","volume":"38","author":"H. Edelsbrunner","year":"1989","unstructured":"Herbert Edelsbrunner, L. Guibas; Topologically sweeping an arrangement; J. Comput. System Sci. 38, pp. 165\u2013194, 1989.","journal-title":"J. Comput. System Sci."},{"key":"16_CR8","unstructured":"S. Eidenbenz and P. Widmayer; An Approximation Algorithm for Minimum Convex Cover with Logarithmic Performance Guarantee; manuscript, to appear."},{"key":"16_CR9","unstructured":"S. Eidenbenz, C. Stamm, and P. Widmayer; Inapproximability of some Art Gallery Problems; Proc. 10th Canadian Conf. Computational Geometry, pp. 64\u201365, 1998."},{"key":"16_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/3-540-68530-8_16","volume-title":"(ESA\u201998)","author":"S. Eidenbenz","year":"1998","unstructured":"S. Eidenbenz, C. Stamm, and P. Widmayer; Positioning Guards at Fixed Height above a Terrain-An Optimum Inapproximability Result; Lecture Notes in Computer Science, Vol. 1461 (ESA\u201998), pp. 187\u2013198, 1998."},{"key":"16_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/3-540-49381-6_45","volume-title":"(ISAAC\u201998)","author":"S. Eidenbenz","year":"1998","unstructured":"S. Eidenbenz; Inapproximability Results for Guarding Polygons without Holes; Lecture Notes in Computer Science, Vol. 1533 (ISAAC\u201998), pp. 427\u2013436, 1998."},{"key":"16_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1007\/3-540-46632-0_20","volume-title":"(ISAAC\u201999)","author":"S. Eidenbenz","year":"1999","unstructured":"S. Eidenbenz; How Many People Can Hide in a Terrain ?; Lecture Notes in Computer Science 1741 (ISAAC\u201999), pp. 184\u2013194, 1999."},{"key":"16_CR13","doi-asserted-by":"crossref","unstructured":"H. Everett, D. Corneil; Negative Results on Characterizing Visibility Graphs; Computational Geometry 5, pp. 51\u201363, 1995.","DOI":"10.1016\/0925-7721(95)00021-Z"},{"key":"16_CR14","unstructured":"S. Ghosh; Approximation algorithms for Art Gallery Problems; Proc. of the Canadian Information Processing Society Congress, 1987."},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"S. Ghosh; On Recognizing and Characterizing Visibility Graphs of Simple Polygons; Discrete Comput Geom 17, pp. 143\u2013162, 1997.","DOI":"10.1007\/BF02770871"},{"key":"16_CR16","unstructured":"J. Hastad; Clique is hard to approximate within n 1-\u2208 ; Proc. of the Symposium on Foundations of Computer Science, 1996."},{"key":"16_CR17","doi-asserted-by":"crossref","unstructured":"J. Hershberger; Finding the Visibility Graph of a Polygon in Time Proportional to its Size; Proc. of the 3rd Annual ACM Symposium on Computational Geometry, Waterloo, pp. 11\u201320, 1987.","DOI":"10.1145\/41958.41960"},{"key":"16_CR18","unstructured":"D. Hochbaum; Approximating Covering and Packing Problems: Set Cover, Vertex Cover, Independent Set, and Related Problems; in: Approximation Algorithms for NP-Hard Problems (ed. Dorit Hochbaum), PWS Publishing Company, pp. 94\u2013143, 1996."},{"key":"16_CR19","doi-asserted-by":"crossref","unstructured":"D. T. Lee and A. K. Lin; Computational Complexity of Art Gallery Problems; IEEE Trans. Info. Th, pp. 126\u2013282, IT-32, 1986.","DOI":"10.1109\/TIT.1986.1057165"},{"key":"16_CR20","doi-asserted-by":"crossref","unstructured":"J. O\u2019Rourke and K. J. Supowit; Some NP-hard Polygon Decomposition Problems; IEEE Transactions on Information Theory, Vol IT-29, No. 2, 1983.","DOI":"10.1109\/TIT.1983.1056648"},{"key":"16_CR21","volume-title":"Art Gallery Theorems and Algorithms","author":"J. O\u2019Rourke","year":"1987","unstructured":"J. O\u2019Rourke; Art Gallery Theorems and Algorithms; Oxford University Press, New York (1987)."},{"key":"16_CR22","doi-asserted-by":"crossref","unstructured":"J. O\u2019Rourke; Open problems in the combinatorics of visibility and illumination; inAdvances in Discrete and Computational Geometry, eds. B. Chazelle and J. E. Goodman and R. Pollack, (Contemporary Mathematics) American Mathematical Society, Providence, pp. 237\u2013243, 1998.","DOI":"10.1090\/conm\/223\/03140"},{"key":"16_CR23","doi-asserted-by":"crossref","unstructured":"C.H. Papadimitriou and M. Yannakakis; Optimization, approximation, and complexity classes; Proc. 20th ACM Symposium on the Theory of Computing, pp. 229\u2013234, 1988.","DOI":"10.1145\/62212.62233"},{"key":"16_CR24","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0304-3975(95)95693-E","volume":"140","author":"L. Prasad","year":"1995","unstructured":"L. Prasad, S.S. Iyengar; A note on the combinatorial structure of the visibility graph in simple polygons; Theoretical Computer Science 140, pp. 249\u2013263, 1995.","journal-title":"Theoretical Computer Science"},{"key":"16_CR25","doi-asserted-by":"crossref","unstructured":"T. Shermer; Recent results in Art Galleries; Proc. of the IEEE, 1992.","DOI":"10.1109\/5.163407"},{"key":"16_CR26","first-page":"109","volume":"42","author":"T. Shermer","year":"1989","unstructured":"T. Shermer; Hiding People in Polygons; Comuting 42, pp. 109\u2013131, 1989.","journal-title":"Comuting"},{"key":"16_CR27","unstructured":"J. Urrutia; Art gallery and Illumination Problems; in Handbook on Computational Geometry, edited by J.-R. Sack and J. Urrutia, 1998."}],"container-title":["Lecture Notes in Computer Science","Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44929-9_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T18:40:51Z","timestamp":1556390451000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44929-9_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540678236","9783540449294"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-44929-9_16","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}