An algorithm for the difference between set covers
- 作者：D.S. Franzblau ; G. Xenakis
- 关键词：Set cover ; Difference ; Hypercube ; Face ; Rectilinear polygon ; Rectangle ; Distributive lattice ; Pseudocomplement
- 刊名：Discrete Applied Mathematics
- 出版年：2008
- 期刊代码：46_0166218x
- 类别：cp
- 出版时间：28 May 2008
- 卷：156
- 期：10
- 页码：1623-1632
- 文件大小：736 K
摘要
A set cover for a set S is a collection C of special subsets whose union is S. Given covers 05aca9fb0b396d6bfdab2627ce" title="Click to view the MathML source" alt="Click to view the MathML source">A and a30e433eea5a005b4" title="Click to view the MathML source" alt="Click to view the MathML source">B for two sets, the set-cover difference problem is to construct a new cover for the elements covered by A but not B. 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-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.