{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:43:25Z","timestamp":1725515005620},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540728689"},{"type":"electronic","value":"9783540728702"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72870-2_32","type":"book-chapter","created":{"date-parts":[[2007,6,25]],"date-time":"2007-06-25T12:53:10Z","timestamp":1182775990000},"page":"337-345","source":"Crossref","is-referenced-by-count":0,"title":["Approximating the Maximum Independent Set and Minimum Vertex Coloring on Box Graphs"],"prefix":"10.1007","author":[{"given":"Xin","family":"Han","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuo","family":"Iwama","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Klein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Lingas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"32_CR1","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":"32_CR2","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/j.comgeo.2005.12.001","volume":"34","author":"P.K. Agarwal","year":"2006","unstructured":"Agarwal, P.K., Mustafa, N.H.: Independent set of intersection graphs of convex objects in 2D. Computational Geometry: Theory and Applications\u00a034, 83\u201395 (2006)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"32_CR3","doi-asserted-by":"crossref","first-page":"181","DOI":"10.7146\/math.scand.a-10607","volume":"8","author":"E. Asplund","year":"1960","unstructured":"Asplund, E., Gr\u00fcnbaum, B.: On coloring problem. Mathematica Scandinavica\u00a08, 181\u2013188 (1960)","journal-title":"Mathematica Scandinavica"},{"key":"32_CR4","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1006\/jagm.2001.1188","volume":"41","author":"P. Berman","year":"2001","unstructured":"Berman, P., DasGupta, B., Muthukrishnan, S., Ramaswami, S.: Efficient approximation algorithms for tiling and packing problems with rectangles. Journal of Algorithms\u00a041, 443\u2013470 (2001)","journal-title":"Journal of Algorithms"},{"key":"32_CR5","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.: A note on maximum independent sets in rectangle intersection graphs. Information Processing Letters\u00a089, 19\u201323 (2004)","journal-title":"Information Processing Letters"},{"key":"32_CR6","unstructured":"Chlebik, M., Chlebikov\u00e1, J.: Approximation Hardness of Optimization Problems in Intersection Graphs of d-dimensional Boxes. In: Proc. SODA, pp. 267\u2013276 (2005)"},{"key":"32_CR7","unstructured":"Erlebach, T., Jansen, K., Seidel, E.: Polynomial-Time Approximation Schemes for Geometric Graphs. In: Proc. SODA, pp. 671\u2013679 (2001)"},{"key":"32_CR8","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"12","author":"R.J. Fowler","year":"1981","unstructured":"Fowler, R.J., Paterson, M.S., Tanimoto, S.L.: Optimal packing and covering the plane are NP-complete. Information Processing Letters\u00a012, 133\u2013137 (1981)","journal-title":"Information Processing Letters"},{"key":"32_CR9","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. Journal of Algorithms\u00a04, 310\u2013323 (1983)","journal-title":"Journal of Algorithms"},{"key":"32_CR10","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1109\/TC.1984.1676388","volume":"33","author":"D.T. Lee","year":"1984","unstructured":"Lee, D.T., Leung, J.Y.-T.: On the 2-dimensional channel assignment problem. IEEE Trans. Comput.\u00a033, 2\u20136 (1984)","journal-title":"IEEE Trans. Comput."},{"key":"32_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/3-540-45753-4_19","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"L. Lewin-Eytan","year":"2002","unstructured":"Lewin-Eytan, L., Naor, J., Orda, A.: Routing and Admission Control in Networks with Advance Reservations. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol.\u00a02462, pp. 215\u2013228. Springer, Heidelberg (2002)"},{"key":"32_CR12","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/j.ipl.2004.10.013","volume":"93","author":"A. Lingas","year":"2005","unstructured":"Lingas, A., Wahlen, M.: A note on maximum independent set and related problems on box graphs. Information Processing Letters\u00a093, 169\u2013171 (2005)","journal-title":"Information Processing Letters"},{"key":"32_CR13","unstructured":"Malesinska, E.: Graph-Theoretical Models for Frequency Assignment Problems. PhD Thesis, TU Berlin (1997)"},{"key":"32_CR14","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S0304-3975(98)00336-3","volume":"246","author":"F. Nielsen","year":"2000","unstructured":"Nielsen, F.: Fast stabbing of boxes in high dimensions. Theoretical Computer Science\u00a0246, 53\u201372 (2000)","journal-title":"Theoretical Computer Science"},{"key":"32_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry \u2013 an Introduction","author":"F. Preparata","year":"1985","unstructured":"Preparata, F., Shamos, M.: Computational Geometry \u2013 an Introduction. Springer, New York (1985)"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Aspects in Information and Management"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72870-2_32.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T05:07:18Z","timestamp":1605762438000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72870-2_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540728689","9783540728702"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72870-2_32","relation":{},"subject":[]}}