Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
431163 | Journal of Discrete Algorithms | 2006 | 8 Pages |
Abstract
A family of nonempty sets has the equal union property if there exist two nonempty disjoint subfamilies having equal unions. If every point belongs to the unions, then we say the family has the full equal union property. Recognition of both properties is NP-complete even when restricted to families for which the degree of every point is at most three. In this paper we show that both recognition problems can be solved in polynomial time for families in which there is a bound on the number of points whose degree exceeds two.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
David P. Jacobs, Robert E. Jamison,