{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T07:16:30Z","timestamp":1712301390695},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,10,27]],"date-time":"2015-10-27T00:00:00Z","timestamp":1445904000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"CONICYT-PCHA\/Doctorado Nacional\/2013 (Chile)","award":["63130161"],"award-info":[{"award-number":["63130161"]}]},{"name":"CONICYT-PCHA\/Doctorado Nacional\/2013 (Chile)","award":["63130209"],"award-info":[{"award-number":["63130209"]}]},{"name":"Millennium Nucleus Information and Coordination in Networks ICM\/FIC (Chile)","award":["RC130003"],"award-info":[{"award-number":["RC130003"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2017,2]]},"DOI":"10.1007\/s10878-015-9971-x","type":"journal-article","created":{"date-parts":[[2015,10,27]],"date-time":"2015-10-27T07:00:07Z","timestamp":1445929207000},"page":"403-421","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Matching colored points with rectangles"],"prefix":"10.1007","volume":"33","author":[{"given":"L. E.","family":"Caraballo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C.","family":"Ochoa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"P\u00e9rez-Lantero","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Rojas-Ledesma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,10,27]]},"reference":[{"issue":"1","key":"9971_CR1","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/s00454-008-9099-1","volume":"41","author":"BM \u00c1brego","year":"2009","unstructured":"\u00c1brego BM, Arkin EM, Fern\u00e1ndez-Merchant S, Hurtado F, Kano M, Mitchell JS, Urrutia J (2009) Matching points with squares. Discrete Comput Geom 41(1):77\u201395","journal-title":"Discrete Comput Geom"},{"key":"9971_CR2","doi-asserted-by":"crossref","unstructured":"Adamaszek A, Wiese A (2013) Approximation schemes for maximum weight independent set of rectangles. In: Proceedings of the 2013 IEEE 54th annual symposium on foundations of computer science, FOCS\u201913, pp 400\u2013409","DOI":"10.1109\/FOCS.2013.50"},{"issue":"2","key":"9971_CR3","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/j.comgeo.2005.12.001","volume":"34","author":"PK Agarwal","year":"2006","unstructured":"Agarwal PK, Mustafa NH (2006) Independent set of intersection graphs of convex objects in 2D. Comput Geom 34(2):83\u201395","journal-title":"Comput Geom"},{"issue":"3\u20134","key":"9971_CR4","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/S0925-7721(98)00028-5","volume":"11","author":"PK Agarwal","year":"1998","unstructured":"Agarwal PK, van Kreveld MJ, Suri S (1998) Label placement by maximum independent set in rectangles. Comput Geom 11(3\u20134):209\u2013218","journal-title":"Comput Geom"},{"issue":"3","key":"9971_CR5","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1016\/j.comgeo.2010.10.002","volume":"44","author":"H-K Ahn","year":"2011","unstructured":"Ahn H-K, Bae SW, Demaine ED, Demaine ML, Kim S-S, Korman M, Reinbacher I, Son W (2011) Covering points by disjoint boxes with outliers. Comput Geom 44(3):178\u2013190","journal-title":"Comput Geom"},{"key":"9971_CR6","unstructured":"Alliez P, Devillers O, Snoeyink J (1997) Removing degeneracies by perturbing the problem or the world. Technical report 3316, INRIA"},{"issue":"2","key":"9971_CR7","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/j.comgeo.2008.05.001","volume":"42","author":"S Bereg","year":"2009","unstructured":"Bereg S, Mutsanas N, Wolff A (2009) Matching points with rectangles and squares. Comput Geom 42(2):93\u2013108","journal-title":"Comput Geom"},{"key":"9971_CR8","doi-asserted-by":"crossref","unstructured":"Chalermsook P (2011) Coloring and maximum independent set of rectangles. In: Approximation, randomization, and combinatorial optimization. Algorithms and techniques. LNCS vol 6845. Springer, Berlin, pp 123\u2013134","DOI":"10.1007\/978-3-642-22935-0_11"},{"key":"9971_CR9","doi-asserted-by":"crossref","unstructured":"Chalermsook P, Chuzhoy J (2009) Maximum independent set of rectangles. In: Proceedings of the twentieth annual ACM-SIAM symposium on discrete algorithms, SODA\u201909, Philadelphia, pp 892\u2013901","DOI":"10.1137\/1.9781611973068.97"},{"issue":"2","key":"9971_CR10","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1016\/S0196-6774(02)00294-8","volume":"46","author":"TM Chan","year":"2003","unstructured":"Chan TM (2003) Polynomial-time approximation schemes for packing and piercing fat objects. J Algorithms 46(2):178\u2013189","journal-title":"J Algorithms"},{"issue":"1","key":"9971_CR11","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/j.ipl.2003.09.019","volume":"89","author":"TM Chan","year":"2004","unstructured":"Chan TM (2004) A note on maximum independent sets in rectangle intersection graphs. Inf Process Lett 89(1):19\u201323","journal-title":"Inf Process Lett"},{"issue":"2","key":"9971_CR12","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/s00454-012-9417-5","volume":"48","author":"TM Chan","year":"2012","unstructured":"Chan TM, Har-Peled S (2012) Approximation algorithms for maximum independent set of pseudo-disks. Discrete Comput Geom 48(2):373\u2013392","journal-title":"Discrete Comput Geom"},{"issue":"1","key":"9971_CR13","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/S0925-7721(01)00007-4","volume":"19","author":"A Dumitrescu","year":"2001","unstructured":"Dumitrescu A, Kaye R (2001) Matching colored points in the plane: some new results. Comput Geom 19(1):69\u201385","journal-title":"Comput Geom"},{"key":"9971_CR14","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/S0012-365X(99)00201-0","volume":"211","author":"A Dumitrescu","year":"2000","unstructured":"Dumitrescu A, Steiger WL (2000) On a matching problem in the plane. Discrete Math 211:183\u2013195","journal-title":"Discrete Math"},{"issue":"6","key":"9971_CR15","doi-asserted-by":"crossref","first-page":"1302","DOI":"10.1137\/S0097539702402676","volume":"34","author":"T Erlebach","year":"2005","unstructured":"Erlebach T, Jansen K, Seidel E (2005) Polynomial-time approximation schemes for geometric intersection graphs. SIAM J Comput 34(6):1302\u20131323","journal-title":"SIAM J Comput"},{"issue":"3","key":"9971_CR16","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"12","author":"RJ Fowler","year":"1981","unstructured":"Fowler RJ, Paterson M, Tanimoto SL (1981) Optimal packing and covering in the plane are NP-complete. Inf Process Lett 12(3):133\u2013137","journal-title":"Inf Process Lett"},{"key":"9971_CR17","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/S0304-0208(08)72943-8","volume":"88","author":"M Gr\u00f6tschel","year":"1984","unstructured":"Gr\u00f6tschel M, Lov\u00e1sz L, Schrijver A (1984) Polynomial algorithms for perfect graphs. Top Perfect Graphs 88:325\u2013356","journal-title":"Top Perfect Graphs"},{"issue":"4","key":"9971_CR18","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1016\/0196-6774(83)90012-3","volume":"4","author":"H Imai","year":"1983","unstructured":"Imai H, Asano T (1983) Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane. J Algorithms 4(4):310\u2013323","journal-title":"J Algorithms"},{"key":"9971_CR19","unstructured":"Khanna S, Muthukrishnan S, Paterson M (1998) On approximating rectangle tiling and packing. In: Proceedings of the ninth annual ACM-SIAM symposium on discrete algorithms, vol\u00a095 SODA\u201998. SIAM, p 384"},{"issue":"3","key":"9971_CR20","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1137\/0405033","volume":"5","author":"DE Knuth","year":"1992","unstructured":"Knuth DE, Raghunathan A (1992) The problem of compatible representatives. SIAM J Discret Math 5(3):422\u2013427","journal-title":"SIAM J Discret Math"},{"issue":"1","key":"9971_CR21","first-page":"85","volume":"31","author":"J Kratochv\u00edl","year":"1990","unstructured":"Kratochv\u00edl J, Ne\u0161et\u0159il J (1990) Independent set and clique problems in intersection-defined classes of graphs. Commen Math Univ Carolinae 31(1):85\u201393","journal-title":"Commen Math Univ Carolinae"},{"key":"9971_CR22","series-title":"Problem books in mathematics","volume-title":"Problem-solving through problems","author":"LC Larson","year":"1990","unstructured":"Larson LC (1990) Problem-solving through problems., Problem books in mathematicsSpringer, Berlin"},{"issue":"4","key":"9971_CR23","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/s00453-004-1114-1","volume":"40","author":"L Lewin-Eytan","year":"2004","unstructured":"Lewin-Eytan L, Naor J, Orda A (2004) Admission control in networks with advance reservations. Algorithmica 40(4):293\u2013304","journal-title":"Algorithmica"},{"issue":"2","key":"9971_CR24","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/1346330.1346336","volume":"55","author":"W Mulzer","year":"2008","unstructured":"Mulzer W, Rote G (2008) Minimum-weight triangulation is NP-hard. J ACM 55(2):11","journal-title":"J ACM"},{"issue":"9","key":"9971_CR25","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1109\/81.414831","volume":"42","author":"CS Rim","year":"1995","unstructured":"Rim CS, Nakajima K (1995) On rectangle intersection and overlap graphs. IEEE Trans Circ Syst 42(9):549\u2013553","journal-title":"IEEE Trans Circ Syst"},{"key":"9971_CR26","doi-asserted-by":"crossref","unstructured":"Soto JA, Telha C (2011) Jump number of two-directional orthogonal ray graphs. In: Integer programming and combinatorial optimization. LNCS, vol 6655. Springer, Berlin, pp 389\u2013403","DOI":"10.1007\/978-3-642-20807-2_31"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-015-9971-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-015-9971-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-015-9971-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-015-9971-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:23:28Z","timestamp":1559262208000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-015-9971-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,27]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,2]]}},"alternative-id":["9971"],"URL":"https:\/\/doi.org\/10.1007\/s10878-015-9971-x","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,10,27]]}}}