An algorithm for the difference between set covers |
| |
Authors: | DS Franzblau |
| |
Institution: | Department of Mathematics, CUNY/College of Staten Island, Staten Island, NY 10314, USA |
| |
Abstract: | A set cover for a set S is a collection C of special subsets whose union is S. Given covers A and 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. |
| |
Keywords: | primary 05B40 68R99 secondary 68U05 52C15 52C17 06D99 |
本文献已被 ScienceDirect 等数据库收录! |
|