Independent Sets and Hitting Sets of Bicolored Rectangular Families

Simple item page
dc.coverageDOI: 10.1007/s00453-021-00810-1
dc.creatorSoto, José A.
dc.creatorTelha, Claudio
dc.date2021
dc.date.accessioned05-01-2026 18:12
dc.date.available05-01-2026 18:12
dc.description<p>A bicolored rectangular family BRF is the collection of all axis-parallel rectangles formed by selecting a bottom-left corner from a finite set of points A and an upper-right corner from a finite set of points B. We devise a combinatorial algorithm to compute the maximum independent set and the minimum hitting set of a BRF that runs in O(n2.5logn)-time, where n= | A| + | B|. This result significantly reduces the gap between the ? (n<sup>7</sup>) -time algorithm by Benczúr (Discrete Appl Math 129 (2–3):233–262, 2003) for the more general problem of finding directed covers of pairs of sets, and the O(n<sup>2</sup>) -time algorithms of Franzblau and Kleitman (Inf Control 63(3):164–189, 1984) and Knuth (ACM J Exp Algorithm 1:1, 1996) for BRFs where the points of A lie on an anti-diagonal line. Furthermore, when the bicolored rectangular family is weighted, we show that the problem of finding the maximum weight of an independent set is NP-hard, and provide efficient algorithms to solve it on important subclasses.</p>eng
dc.descriptionA bicolored rectangular family BRF is the collection of all axis-parallel rectangles formed by selecting a bottom-left corner from a finite set of points A and an upper-right corner from a finite set of points B. We devise a combinatorial algorithm to compute the maximum independent set and the minimum hitting set of a BRF that runs in O(n2.5logn)-time, where n= | A| + | B|. This result significantly reduces the gap between the ? (n7) -time algorithm by Benczúr (Discrete Appl Math 129 (2–3):233–262, 2003) for the more general problem of finding directed covers of pairs of sets, and the O(n2) -time algorithms of Franzblau and Kleitman (Inf Control 63(3):164–189, 1984) and Knuth (ACM J Exp Algorithm 1:1, 1996) for BRFs where the points of A lie on an anti-diagonal line. Furthermore, when the bicolored rectangular family is weighted, we show that the problem of finding the maximum weight of an independent set is NP-hard, and provide efficient algorithms to solve it on important subclasses.eng
dc.descriptionA bicolored rectangular family BRF is the collection of all axis-parallel rectangles formed by selecting a bottom-left corner from a finite set of points A and an upper-right corner from a finite set of points B. We devise a combinatorial algorithm to compute the maximum independent set and the minimum hitting set of a BRF that runs in O(n2.5logn)-time, where n= | A| + | B|. This result significantly reduces the gap between the ? (n7) -time algorithm by Benczúr (Discrete Appl Math 129 (2–3):233–262, 2003) for the more general problem of finding directed covers of pairs of sets, and the O(n2) -time algorithms of Franzblau and Kleitman (Inf Control 63(3):164–189, 1984) and Knuth (ACM J Exp Algorithm 1:1, 1996) for BRFs where the points of A lie on an anti-diagonal line. Furthermore, when the bicolored rectangular family is weighted, we show that the problem of finding the maximum weight of an independent set is NP-hard, and provide efficient algorithms to solve it on important subclasses.spa
dc.identifierhttps://investigadores.uandes.cl/en/publications/dac150b6-4c4d-4cc5-aa09-591b9c4c06a0
dc.languageeng
dc.rightsinfo:eu-repo/semantics/restrictedAccess
dc.sourcevol.83 (2021) nr.6 p.1918-1952
dc.subjectAxis-parallel rectangles
dc.subjectHitting set
dc.subjectIndependent set
dc.subjectJump number
dc.subjectAxis-parallel rectangles
dc.subjectHitting set
dc.subjectIndependent set
dc.subjectJump number
dc.titleIndependent Sets and Hitting Sets of Bicolored Rectangular Familieseng
dc.typeArticleeng
dc.typeArtículospa
Files
Collections
Doctorado en Ciencias de la Ingeniería (DOCI)