{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T19:51:27Z","timestamp":1771617087993,"version":"3.50.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,2,17]],"date-time":"2021-02-17T00:00:00Z","timestamp":1613520000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,2,17]],"date-time":"2021-02-17T00:00:00Z","timestamp":1613520000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"ANID-CHILE","award":["FONDECYT 1181180"],"award-info":[{"award-number":["FONDECYT 1181180"]}]},{"name":"ANID-CHILE","award":["PIA AFB170001"],"award-info":[{"award-number":["PIA AFB170001"]}]},{"name":"ANID-CHILE","award":["FONDECYT 11200616"],"award-info":[{"award-number":["FONDECYT 11200616"]}]},{"name":"Fonds Speciaux de Recherche. French Community of Belgium"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1007\/s00453-021-00810-1","type":"journal-article","created":{"date-parts":[[2021,2,19]],"date-time":"2021-02-19T13:37:49Z","timestamp":1613741869000},"page":"1918-1952","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Independent Sets and Hitting Sets of Bicolored Rectangular Families"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2219-8401","authenticated-orcid":false,"given":"Jos\u00e9 A.","family":"Soto","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5493-5889","authenticated-orcid":false,"given":"Claudio","family":"Telha","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,2,17]]},"reference":[{"key":"810_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, pp. 400\u2013409. IEEE (2013)","DOI":"10.1109\/FOCS.2013.50"},{"key":"810_CR2","doi-asserted-by":"crossref","unstructured":"Alman, J., Williams, V.V.: A refined laser method and faster matrix multiplication. In: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 522\u2013539. SIAM (2021)","DOI":"10.1137\/1.9781611976465.32"},{"key":"810_CR3","unstructured":"Amilhastre, J., Janssen, P., Vilarem, M.-C.: Computing a minimum biclique cover is polynomial for bipartite domino-free graphs. In: Saks, M. (ed.) Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 36\u201342. SIAM (1997)"},{"issue":"7","key":"810_CR4","doi-asserted-by":"publisher","first-page":"3248","DOI":"10.1137\/090762968","volume":"39","author":"B Aronov","year":"2010","unstructured":"Aronov, B., Ezra, E., Sharir, M.: Small-size $$\\epsilon$$-nets for axis-parallel rectangles and boxes. SIAM J. Comput. 39(7), 3248\u20133282 (2010)","journal-title":"SIAM J. Comput."},{"key":"810_CR5","doi-asserted-by":"crossref","unstructured":"Bencz\u00far, A., F\u00f6rster, J., Kir\u00e1ly, Z.: Dilworth\u2019s theorem and its application for path systems of a cycle. Implementation and analysis. In: Ne\u0161et\u0159il, J. (ed.) Algorithms-ESA\u2019 99. Lecture Notes in Computer Science, vol. 1643, pp. 693\u2013693. Springer, Berlin, Heidelberg (1999)","DOI":"10.1007\/3-540-48481-7_43"},{"issue":"2\u20133","key":"810_CR6","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/S0166-218X(02)00570-X","volume":"129","author":"AA Bencz\u00far","year":"2003","unstructured":"Bencz\u00far, A.A.: Pushdown-reduce: an algorithm for connectivity augmentation and poset covering problems. Discrete Appl. Math. 129(2\u20133), 233\u2013262 (2003)","journal-title":"Discrete Appl. Math."},{"key":"810_CR7","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A.: The jump number problem for biconvex graphs and rectangle covers of rectangular regions. In: Csirik, J., Demetrovics, J., G\u00e9cseg, F. (eds.) Fundamentals of Computation Theory, Volume 380 of Lecture Notes in Computer Science, pp. 68\u201377. Springer (1989)","DOI":"10.1007\/3-540-51498-8_7"},{"key":"810_CR8","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph cCasses: A Survey","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph cCasses: A Survey. Society for Industrial and Applied Mathematics, Philadelphia (1999)"},{"issue":"4","key":"810_CR9","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1137\/0602042","volume":"2","author":"S Chaiken","year":"1981","unstructured":"Chaiken, S., Kleitman, D.J., Saks, M., Shearer, J.: Covering regions by rectangles. SIAM J. Algebr. Discrete Methods 2(4), 394\u2013410 (1981)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"810_CR10","doi-asserted-by":"crossref","unstructured":"Chalermsook, P.: Coloring and maximum independent set of rectangles. In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds.) Approx-Random, Volume 6845 of Lecture Notes in Computer Science, pp. 123\u2013134. Springer (2011)","DOI":"10.1007\/978-3-642-22935-0_11"},{"key":"810_CR11","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Chuzhoy, J.: Maximum independent set of rectangles. In:\u00a0Mathieu, C. (ed.)\u00a0Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 892\u2013901. SIAM (2009)","DOI":"10.1137\/1.9781611973068.97"},{"issue":"2","key":"810_CR12","doi-asserted-by":"publisher","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."},{"key":"810_CR13","first-page":"183","volume":"16","author":"G Chaty","year":"1979","unstructured":"Chaty, G., Chein, M.: Ordered matchings and matchings without alternating cycles in bipartite graphs. Utilitas Math. 16, 183\u2013187 (1979)","journal-title":"Utilitas Math."},{"key":"810_CR14","doi-asserted-by":"publisher","first-page":"51","DOI":"10.4007\/annals.2006.164.51","volume":"164","author":"M Chudnovsky","year":"2006","unstructured":"Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164, 51\u2013229 (2006)","journal-title":"Ann. Math."},{"key":"810_CR15","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Ene, A.: On approximating maximum independent set of rectangles. In: Dinur, I. (ed) IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9\u201311 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pp. 820\u2013829. IEEE Computer Society (2016)","DOI":"10.1109\/FOCS.2016.92"},{"key":"810_CR16","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1007\/s00454-014-9661-y","volume":"53","author":"J Correa","year":"2015","unstructured":"Correa, J., Feuilloley, L., P\u00e9rez-Lantero, P., Soto, J.A.: Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity. Discrete Comput. Geom. 53, 344\u2013365 (2015)","journal-title":"Discrete Comput. Geom."},{"key":"810_CR17","doi-asserted-by":"crossref","unstructured":"Dahlhaus, E.: The computation of the jump number of convex graphs. In: Bouchitt\u00e9, V., Morvan, M. (eds.) ORDAL, Volume 831 of Lecture Notes in Computer Science, pp. 176\u2013185. Springer (1994)","DOI":"10.1007\/BFb0019434"},{"issue":"8","key":"810_CR18","first-page":"391","volume":"27","author":"H Fauck","year":"1991","unstructured":"Fauck, H.: Covering polygons with rectangles via edge coverings of bipartite permutation graphs. Elektronische Informationsverarbeitung und Kybernetik 27(8), 391\u2013409 (1991)","journal-title":"Elektronische Informationsverarbeitung und Kybernetik"},{"key":"810_CR19","volume-title":"Flow in Networks","author":"L Ford","year":"1962","unstructured":"Ford, L., Fulkerson, D.: Flow in Networks. Princeton University Press, Princeton (1962)"},{"issue":"3","key":"810_CR20","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"12","author":"R Fowler","year":"1981","unstructured":"Fowler, R., Paterson, M., Tanimoto, S.: Optimal packing and covering in the plane are np-complete. Inf. Process. Lett. 12(3), 133\u2013137 (1981)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"810_CR21","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1006\/jctb.1998.1877","volume":"75","author":"A Frank","year":"1999","unstructured":"Frank, A.: Finding minimum generators of path systems. J. Comb. Theory Ser. B 75(2), 237\u2013244 (1999)","journal-title":"J. Comb. Theory Ser. B"},{"key":"810_CR22","doi-asserted-by":"crossref","unstructured":"Frank, A.: Finding minimum weighted generators of a path system. In: Ronald, J.N., Graham, L., Kratochv\u00edl, J. Roberts, F.S. (eds.) Contemporary Trends in Discrete Mathematics, Volume\u00a049 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 129\u2013137. American Mathematical Society (1999)","DOI":"10.1090\/dimacs\/049\/07"},{"issue":"1","key":"810_CR23","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1006\/jctb.1995.1044","volume":"65","author":"A Frank","year":"1995","unstructured":"Frank, A., Jord\u00e1n, T.: Minimal edge-coverings of pairs of sets. J. Comb. Theory Ser. B 65(1), 73\u2013110 (1995)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3","key":"810_CR24","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/S0019-9958(84)80012-1","volume":"63","author":"DS Franzblau","year":"1984","unstructured":"Franzblau, D.S., Kleitman, D.J.: An algorithm for covering polygons with rectangles. Inf. Control 63(3), 164\u2013189 (1984)","journal-title":"Inf. Control"},{"issue":"1","key":"810_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0095-8956(84)90039-X","volume":"37","author":"E Gy\u00f6ri","year":"1984","unstructured":"Gy\u00f6ri, E.: A minimax theorem on intervals. J. Comb. Theory Ser. B 37(1), 1\u20139 (1984)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"4","key":"810_CR26","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J Hopcroft","year":"1973","unstructured":"Hopcroft, J., Karp, R.: An $$n^{5\/2}$$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"810_CR27","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 4(4), 310\u2013323 (1983)","journal-title":"J. Algorithms"},{"key":"810_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/235141.235146","volume":"1","author":"DE Knuth","year":"1996","unstructured":"Knuth, D.E.: Irredundant intervals. ACM J. Exp. Algorithm. 1, 1 (1996)","journal-title":"ACM J. Exp. Algorithm."},{"key":"810_CR29","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511977152","volume-title":"Iterative Methods in Combinatorial Optimization","author":"L-C Lau","year":"2011","unstructured":"Lau, L.-C., Ravi, R., Singh, M.: Iterative Methods in Combinatorial Optimization, 1st edn. Cambridge University Press, New York (2011)","edition":"1"},{"issue":"2","key":"810_CR30","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0095-8956(72)90045-7","volume":"13","author":"L Lov\u00e1sz","year":"1972","unstructured":"Lov\u00e1sz, L.: A characterization of perfect graphs. J. Comb. Theory Ser. B 13(2), 95\u201398 (1972)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"810_CR31","doi-asserted-by":"publisher","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"},{"key":"810_CR32","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings via gaussian elimination. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2004, pp. 248\u2013255. IEEE (2004)"},{"key":"810_CR33","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/BF00383169","volume":"7","author":"H M\u00fcller","year":"1990","unstructured":"M\u00fcller, H.: Alternating cycle-free matchings. Order 7, 11\u201321 (1990)","journal-title":"Order"},{"issue":"1\u20133","key":"810_CR34","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0012-365X(94)00350-R","volume":"149","author":"H M\u00fcller","year":"1996","unstructured":"M\u00fcller, H.: On edge perfectness and classes of bipartite graphs. Discrete Math. 149(1\u20133), 159\u2013187 (1996)","journal-title":"Discrete Math."},{"issue":"5","key":"810_CR35","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1016\/1385-7258(77)90055-5","volume":"80","author":"J Orlin","year":"1977","unstructured":"Orlin, J.: Contentment in graph theory: covering graphs with cliques. Indag. Math. (Proc.) 80(5), 406\u2013424 (1977)","journal-title":"Indag. Math. (Proc.)"},{"key":"810_CR36","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol. 24. Springer, Berlin (2003)"},{"issue":"15","key":"810_CR37","doi-asserted-by":"publisher","first-page":"1650","DOI":"10.1016\/j.dam.2010.06.002","volume":"158","author":"AMS Shrestha","year":"2010","unstructured":"Shrestha, A.M.S., Tayu, S., Ueno, S.: On orthogonal ray graphs. Discrete Appl. Math. 158(15), 1650\u20131659 (2010)","journal-title":"Discrete Appl. Math."},{"key":"810_CR38","doi-asserted-by":"crossref","unstructured":"Soto, J., Telha, C.:\u00a0Jump number of two-directional orthogonal ray graphs. In: G\u00fcnl\u00fck, O., Woeginger, G.J. (eds.) Integer Programming and Combinatoral Optimization, Volume 6655 of Lecture Notes in Computer Science, pp. 389\u2013403. Springer (2011)","DOI":"10.1007\/978-3-642-20807-2_31"},{"key":"810_CR39","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/BF00340778","volume":"3","author":"G Steiner","year":"1987","unstructured":"Steiner, G., Stewart, L.K.: A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders. Order 3, 359\u2013367 (1987)","journal-title":"Order"},{"key":"810_CR40","doi-asserted-by":"crossref","unstructured":"V\u00e9gh, L.\u00a0A., Bencz\u00far. A.A.: Primal-dual approach for directed vertex connectivity augmentation and generalizations. ACM Trans. Algorithms 4(2). Article 20 (2008)","DOI":"10.1145\/1361192.1361197"},{"issue":"3","key":"810_CR41","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1145\/3828.3839","volume":"32","author":"DE Willard","year":"1985","unstructured":"Willard, D.E., Lueker, G.S.: Adding range restriction capability to dynamic data structures. J. ACM 32(3), 597\u2013617 (1985)","journal-title":"J. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00810-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00810-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00810-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,25]],"date-time":"2021-05-25T10:06:34Z","timestamp":1621937194000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00810-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,17]]},"references-count":41,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["810"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00810-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,17]]},"assertion":[{"value":"24 August 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 January 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 February 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}