{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T18:59:40Z","timestamp":1769972380364,"version":"3.49.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,1,21]],"date-time":"2015-01-21T00:00:00Z","timestamp":1421798400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2015,3]]},"DOI":"10.1007\/s00454-014-9661-y","type":"journal-article","created":{"date-parts":[[2015,1,20]],"date-time":"2015-01-20T20:37:12Z","timestamp":1421786232000},"page":"344-365","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":24,"title":["Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line: Algorithms and Complexity"],"prefix":"10.1007","volume":"53","author":[{"given":"Jos\u00e9","family":"Correa","sequence":"first","affiliation":[]},{"given":"Laurent","family":"Feuilloley","sequence":"additional","affiliation":[]},{"given":"Pablo","family":"P\u00e9rez-Lantero","sequence":"additional","affiliation":[]},{"given":"Jos\u00e9 A.","family":"Soto","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,1,21]]},"reference":[{"key":"9661_CR1","doi-asserted-by":"crossref","unstructured":"Adamaszek, A., Wiese, A.: Approximation schemes for maximum weight independent set of rectangles. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pp. 400\u2013409. IEEE, New York (2013)","DOI":"10.1109\/FOCS.2013.50"},{"key":"9661_CR2","unstructured":"Ahmadinejad, A., Zarrabi-Zadeh, H.: The maximum disjoint set of boundary rectangles. In: Proceedings of the Twenty Sixth Canadian Conference on Computational Geometry (2014)"},{"issue":"7","key":"9661_CR3","doi-asserted-by":"crossref","first-page":"3248","DOI":"10.1137\/090762968","volume":"39","author":"B Aronov","year":"2010","unstructured":"Aronov, B., Ezra, E., Sharir, M.: Small-size $$\\varepsilon $$ \u03b5 -nets for axis-parallel rectangles and boxes. SIAM J. Comput. 39(7), 3248\u20133282 (2010)","journal-title":"SIAM J. Comput."},{"key":"9661_CR4","unstructured":"Asano, T.: Difficulty of the maximum independent set problem on intersection graphs of geometric objects. In: 6th ICTAG (1991)"},{"key":"9661_CR5","unstructured":"Caraballo, L.E., Ochoa, C., P\u00e9rez-Lantero, P., Rojas-Ledesma, J.: Matching colored points with rectangles. http:\/\/arxiv.org\/abs\/1309.3696 (2014)"},{"key":"9661_CR6","unstructured":"Catanzaro, D., Chaplick, S., Felsner, S., Halld\u00f3rsson, B.V., Halld\u00f3rsson, M.M., Hixon, T., Stacho, J.: Max point-tolerance graphs. http:\/\/www.user.tu-berlin.de\/chaplick\/mpt.pdf (2013). Accessed Apr 2014"},{"key":"9661_CR7","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Chuzhoy, J.: Maximum independent set of rectangles. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 892\u2013901. Society for Industrial and Applied Mathematics, Philadelphia (2009)","DOI":"10.1137\/1.9781611973068.97"},{"issue":"2","key":"9661_CR8","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/s00454-012-9417-5","volume":"48","author":"TM Chan","year":"2012","unstructured":"Chan, T.M., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. Discrete Comput. Geom. 48(2), 373\u2013392 (2012)","journal-title":"Discrete Comput. Geom."},{"issue":"9","key":"9661_CR9","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1016\/j.comgeo.2013.05.008","volume":"46","author":"V Chepoi","year":"2013","unstructured":"Chepoi, V., Felsner, S.: Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve. Comput. Geom. 46(9), 1036\u20131041 (2013)","journal-title":"Comput. Geom."},{"key":"9661_CR10","unstructured":"Cibulka, J., Hladk\u00fd, J., Kazda, A., Lidick\u00fd, B., Ondr\u00e1\u010dkov\u00e1, E., Tancer, M., Jel\u00ednek, V.: Personal Communication (2011)"},{"issue":"1","key":"9661_CR11","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/0012-365X(93)90587-J","volume":"120","author":"DG Fon-Der-Flaass","year":"1993","unstructured":"Fon-Der-Flaass, D.G., Kostochka, A.V.: Covering boxes by points. Discrete Math. 120(1), 269\u2013275 (1993)","journal-title":"Discrete Math."},{"issue":"3","key":"9661_CR12","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"12","author":"RJ Fowler","year":"1981","unstructured":"Fowler, R.J., Paterson, M.S., Tanimoto, S.L.: Optimal packing and covering in the plane are NP-complete. Inf. Process. Lett. 12(3), 133\u2013137 (1981)","journal-title":"Inf. Process. Lett."},{"key":"9661_CR13","volume-title":"Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics","author":"MC Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics, vol. 57. North-Holland, Amsterdam (2004)"},{"issue":"2","key":"9661_CR14","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0012-365X(85)90045-7","volume":"55","author":"A Gy\u00e1rf\u00e1s","year":"1985","unstructured":"Gy\u00e1rf\u00e1s, A., Lehel, J.: Covering and coloring problems for relatives of intervals. Discrete Math. 55(2), 167\u2013180 (1985)","journal-title":"Discrete Math."},{"key":"9661_CR15","doi-asserted-by":"crossref","unstructured":"Kong, H., Ma, Q., Yan, T., Wong, M.: An optimal algorithm for finding disjoint rectangles and its applications to pcb routing. In: Proceedings of the Forty Seventh ACM\/EDAC\/IEEE Design Automation Conference, pp. 212\u2013217 (2010)","DOI":"10.1145\/1837274.1837326"},{"key":"9661_CR16","unstructured":"Hixon, T.S.: Hook graphs and more: some contributions to geometric graph theory. Masters thesis, Technische Universit\u00e4t Berlin, Berlin (2013)"},{"issue":"5","key":"9661_CR17","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0020-0190(92)90216-I","volume":"43","author":"JY Hsiao","year":"1992","unstructured":"Hsiao, J.Y., Tang, C.Y., Chang, R.S.: An efficient algorithm for finding a maximum weight 2-independent set on interval graphs. Inf. Process. Lett. 43(5), 229\u2013235 (1992)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"9661_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.: Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane. J. Algorithms 4(4), 310\u2013323 (1983)","journal-title":"J. Algorithms"},{"issue":"2","key":"9661_CR19","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02280661","volume":"23","author":"GY K\u00e1rolyi","year":"1991","unstructured":"K\u00e1rolyi, G.Y.: On point covers of parallel rectangles. Period. Math. Hung. 23(2), 105\u2013107 (1991)","journal-title":"Period. Math. Hung."},{"issue":"3","key":"9661_CR20","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1137\/0405033","volume":"5","author":"DE Knuth","year":"1992","unstructured":"Knuth, D.E., Raghunathan, A.: The problem of compatible representatives. SIAM J. Discrete Math. 5(3), 422\u2013427 (1992)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"9661_CR21","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329\u2013343 (1982)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9661_CR22","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/0095-8956(91)90073-S","volume":"53","author":"A Lubiw","year":"1991","unstructured":"Lubiw, A.: A weighted min-max relation for intervals. J. Comb. Theory Ser. B 53(2), 151\u2013172 (1991)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"4","key":"9661_CR23","doi-asserted-by":"crossref","first-page":"883","DOI":"10.1007\/s00454-010-9285-9","volume":"44","author":"NH Mustafa","year":"2010","unstructured":"Mustafa, N.H., Ray, S.: Improved results on geometric hitting set problems. Discrete Comput. Geom. 44(4), 883\u2013895 (2010)","journal-title":"Discrete Comput. Geom."},{"key":"9661_CR24","doi-asserted-by":"crossref","unstructured":"Soto, J.A., Telha, C.: Jump number of two-directional orthogonal ray graphs. In: Integer Programming and Combinatorial Optimization, pp. 389\u2013403. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-20807-2_31"},{"key":"9661_CR25","unstructured":"Soto, M., Thraves, C.: (c-)And graphs\u2014more than intersection, more than geometric. http:\/\/arxiv.org\/abs\/1306.1957 (2013)"},{"key":"9661_CR26","unstructured":"Wegner, G.: \u00dcber eine kombinatorisch-geometrische frage Hadwiger und Debrunner. Isr. J. Math. 3(4), 187\u2013198 (1965)"},{"issue":"3","key":"9661_CR27","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1137\/0603036","volume":"3","author":"M Yannakakis","year":"1982","unstructured":"Yannakakis, M.: The complexity of the partial order dimension problem. SIAM J. Algebr. Discrete Methods 3(3), 351\u2013358 (1982)","journal-title":"SIAM J. Algebr. Discrete Methods"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-014-9661-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-014-9661-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-014-9661-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,19]],"date-time":"2019-08-19T22:39:23Z","timestamp":1566254363000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-014-9661-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,21]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,3]]}},"alternative-id":["9661"],"URL":"https:\/\/doi.org\/10.1007\/s00454-014-9661-y","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1,21]]}}}