کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418947 | 681728 | 2008 | 10 صفحه PDF | دانلود رایگان |
A set cover for a set SS is a collection CC of special subsets whose union is SS. Given covers AA and BB for two sets, the set-cover difference problem is to construct a new cover for the elements covered by AA but not BB. Applications include testing equivalence of set covers and maintaining a set cover dynamically. In this paper, we solve the set-cover difference problem by defining a difference operation A-BA-B, which turns out to be a pseudocomplement on a distributive lattice. We give an algorithm for constructing this difference, and show how to implement the algorithm for two examples with applications in computer science: face covers on a hypercube, and rectangle covers on a grid. We derive an upper bound on the time complexity of the algorithm, and give upper and lower bounds on complexity for face covers and rectangle covers.
Journal: Discrete Applied Mathematics - Volume 156, Issue 10, 28 May 2008, Pages 1623–1632