{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:10:35Z","timestamp":1761621035145},"reference-count":25,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2010,4]]},"abstract":"<jats:p> Maximum Independent Set (MIS) and its relative Maximum Weight Independent Set (MWIS) are well-known problems in combinatorial optimization; they are NP-hard even in the geometric setting of unit disk graphs. In this paper, we study the Maximum Area Independent Set (MAIS) problem, a natural restricted version of MWIS in disk intersection graphs where the weight equals the disk area. We obtain: (i) Quantitative bounds on the maximum total area of an independent set relative to the union area; (ii) Practical constant-ratio approximation algorithms for finding an independent set with a large total area relative to the union area. <\/jats:p>","DOI":"10.1142\/s0218195910003220","type":"journal-article","created":{"date-parts":[[2010,4,21]],"date-time":"2010-04-21T11:38:07Z","timestamp":1271849887000},"page":"105-118","source":"Crossref","is-referenced-by-count":6,"title":["MAXIMUM AREA INDEPENDENT SETS IN DISK INTERSECTION GRAPHS"],"prefix":"10.1142","volume":"20","author":[{"given":"SERGEY","family":"BEREG","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Texas at Dallas, Richardson, Texas 75083, USA"}]},{"given":"ADRIAN","family":"DUMITRESCU","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Wisconsin \u2013 Milwaukee, Wisconsin 53201-0784, USA"}]},{"given":"MINGHUI","family":"JIANG","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Utah State University, Logan, Utah 84322-4205, USA"}]}],"member":"219","published-online":{"date-parts":[[2012,4,30]]},"reference":[{"key":"rf1","first-page":"61","volume":"21","author":"Ajtai M.","journal-title":"Bulletin de l'Acad\u00e9mie Polonaise des Sciences, S\u00e9rie des Sciences Math\u00e9matiques, Astronomiques et Physiques"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1145\/1041680.1041683"},{"key":"rf5","first-page":"221","volume":"553","author":"Bezdek K.","journal-title":"J. die Reine und Angewandte Mathematik"},{"key":"rf7","volume-title":"Research Problems in Discrete Geometry","author":"Bra\u00df P.","year":"2005"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00294-8"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90358-O"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0963-8"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009381"},{"key":"rf12","unstructured":"P.\u00a0Erd\u0151s, Intuitive Geometry, Colloquia Mathematica Societatis J\u00e1nos Bolyai, Some combinatorial and metric problems in geometry\u00a048, eds. K.\u00a0B\u00f6r\u00f6czky and G. Fejes\u00a0T\u00f3th (North-Holland, Amsterdam, 1987)\u00a0pp. 167\u2013177."},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702402676"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1145\/2455.214106"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230250205"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719802"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1002\/9781118033203"},{"key":"rf18","first-page":"30","volume":"6","author":"Pach J.","journal-title":"Geombinatorics"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(85)90106-2"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"rf21","first-page":"232","volume":"51","author":"Rado R.","journal-title":"Proc. London Math. Soc."},{"key":"rf22","first-page":"243","volume":"53","author":"Rado R.","journal-title":"Proc. London Math. Soc."},{"key":"rf23","first-page":"127","volume":"42","author":"Rado R.","journal-title":"J. London Math. Soc."},{"key":"rf24","doi-asserted-by":"crossref","first-page":"228","DOI":"10.4064\/fm-11-1-228-229","volume":"11","author":"Rado T.","journal-title":"Fundamenta Mathematicae"},{"key":"rf25","volume":"1","author":"Scott P. R.","journal-title":"J. Inequalities in Pure and Appl. Math."},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-002-2897-y"},{"key":"rf27","first-page":"141","volume":"5","author":"Zalgaller V. A.","journal-title":"Matem. Prosveskcheric"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1201\/9781420035346"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195910003220","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T12:21:10Z","timestamp":1565094070000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195910003220"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4]]},"references-count":25,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2012,4,30]]},"published-print":{"date-parts":[[2010,4]]}},"alternative-id":["10.1142\/S0218195910003220"],"URL":"https:\/\/doi.org\/10.1142\/s0218195910003220","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,4]]}}}