{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:56:41Z","timestamp":1725559001747},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540223399"},{"type":"electronic","value":"9783540278108"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27810-8_12","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T13:27:29Z","timestamp":1279027649000},"page":"127-137","source":"Crossref","is-referenced-by-count":1,"title":["Independent Set of Intersection Graphs of Convex Objects in 2D"],"prefix":"10.1007","author":[{"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nabil H.","family":"Mustafa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Erickson, J.: Geometric range searching and its relatives. In: Chazelle, B., Goodman, J.E., Pollack, R. (eds.) Advances in Discrete and Computational Geometry, vol.\u00a0223, pp. 1\u201356 (1999)","DOI":"10.1090\/conm\/223\/03131"},{"key":"12_CR2","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/S0925-7721(98)00028-5","volume":"11","author":"P.K. Agarwal","year":"1998","unstructured":"Agarwal, P.K., van Kreveld, M., Suri, S.: Label placement by maximum independent set in rectangles. Computational Geometry: Theory and Applications\u00a011, 209\u2013218 (1998)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"12_CR3","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM\u00a041, 153\u2013180 (1994)","journal-title":"J. ACM"},{"key":"12_CR4","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/0196-6774(80)90015-2","volume":"1","author":"J.L. Bentley","year":"1980","unstructured":"Bentley, J.L., Saxe, J.B.: Decomposable searching problems I: Static-to-dynamic transformation. J. Algorithms\u00a01, 301\u2013358 (1980)","journal-title":"J. Algorithms"},{"key":"12_CR5","doi-asserted-by":"crossref","unstructured":"Berman, P., Fujito, T.: Approximating independent sets in degree 3 graphs. In: Proc. 4th Workshop on Algorithms and Data Structures, pp. 449\u2013460 (1995)","DOI":"10.1007\/3-540-60220-8_84"},{"key":"12_CR6","doi-asserted-by":"crossref","unstructured":"Boppana, R., Halld\u00f3rsson, M.M.: Approximating maximum independent sets by excluding subgraphs . In: Gilbert, J.R., Karlsson, R. (eds.) Proc. 2nd Scandinavian Workshop on Algorithm Theory, vol.\u00a0447, pp. 13\u201325 (1990)","DOI":"10.1007\/3-540-52846-6_74"},{"key":"12_CR7","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1016\/S0196-6774(02)00294-8","volume":"46","author":"T.M. Chan","year":"2003","unstructured":"Chan, T.M.: Polynomial-time approximation schemes for packing and piercing fat objects. Journal of Algorithms\u00a046, 178\u2013189 (2003)","journal-title":"Journal of Algorithms"},{"key":"12_CR8","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.ipl.2003.09.019","volume":"89","author":"T.M. Chan","year":"2004","unstructured":"Chan, T.M.: Anote onmaximumindependent sets in rectangle intersection graphs, Information. Information Processing Letters\u00a089, 19\u201323 (2004)","journal-title":"Information Processing Letters"},{"key":"12_CR9","doi-asserted-by":"publisher","first-page":"161","DOI":"10.2307\/1969503","volume":"51","author":"P. Dilworth","year":"1950","unstructured":"Dilworth, P.: A decomposition thorem for partially ordered sets. Annals of Mathematics\u00a051, 161\u2013166 (1950)","journal-title":"Annals of Mathematics"},{"key":"12_CR10","unstructured":"Erlebach, T., Jansen, K., Seidel, E.: Polynomial-time approximation schemes for geometric graphs. In: Proceedings of the Twelth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 671\u2013679 (2001)"},{"key":"12_CR11","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, New York (1979)"},{"key":"12_CR12","doi-asserted-by":"crossref","unstructured":"Hastad, J.: Clique is hard to approximate within n1\u2212_, Acta Math., vol.\u00a0182, pp. 105\u2013142 (1999)","DOI":"10.1007\/BF02392825"},{"key":"12_CR13","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1997.0903","volume":"26","author":"H.B. Hunt","year":"1998","unstructured":"Hunt, H.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. J. Algorithms\u00a026, 238\u2013274 (1998)","journal-title":"J. Algorithms"},{"key":"12_CR14","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1016\/0196-6774(83)90012-3","volume":"4","author":"H. Imai","year":"1983","unstructured":"Imai, H., Asano, T.: Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane. J. Algorithms\u00a04, 310\u2013323 (1983)","journal-title":"J. Algorithms"},{"key":"12_CR15","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1006\/jctb.1994.1071","volume":"62","author":"J. Kratochvil","year":"1994","unstructured":"J. Kratochvil and J. Matousek, Intersection graphs of segments, Journal of Combinatorial Theory, Series B, 62 (1994), 289\u2013315.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"12_CR16","unstructured":"E. Malesinska, Graph-theoretical models for frequency assignment problems, Ph.D. Thesis, Technische Universitit Berlin, 1997."},{"key":"12_CR17","doi-asserted-by":"crossref","unstructured":"J. Pach and P. K. Agarwal, Combinatorial Geometry, John Wiley & Sons, New York, NY, 1995.","DOI":"10.1002\/9781118033203"},{"key":"12_CR18","doi-asserted-by":"crossref","unstructured":"J. Pach and G. Tardos, Cutting glass, Proc. 16th Annual Symposium on Computational Geometry, 2000, pp. 360\u2013369.","DOI":"10.1145\/336154.336223"},{"key":"12_CR19","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. H. Papadimitriou","year":"1991","unstructured":"C. H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, J. Comput. System Sci., 43 (1991), 425\u2013440.","journal-title":"J. Comput. System Sci."},{"key":"12_CR20","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1109\/81.414831","volume":"42","author":"C. S. Rim","year":"1995","unstructured":"C. S. Rim and K. Nakajima, On rectangle intersection and overlap graphs, IEEE Transactions on Circuits and Systems, 42 (1995), 549\u2013553.","journal-title":"IEEE Transactions on Circuits and Systems"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27810-8_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T23:21:40Z","timestamp":1605741700000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27810-8_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540223399","9783540278108"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27810-8_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}