Union-member algorithms for non-disjoint sets

[摘要] In this paper we deal with the following problem. We are given a finite set U = {$u_1$,...,$u_n$} and a set [cursive capital 'S'] = {$S_1$,...,$S_m$} of subsets of U. We are also given m-1 UNION instructions that have the form UNION($S_i$,$S_j$) and mean "add the set $S_i \cup S_j$ to the collection and delete $S_i$ and $S_j$." Interspaced among the UNIONs are MEMBER(i,j) questions that mean "does $u_i$ belong to $S_j$?" We present two algorithms that exhibit the trade-off among the three interesting parameters of this problem, which are: 1. Time required to answer one membership question. 2. Time required to perform the m-1 UNIONs altogether. 3. Space. We also give an application of these algorithms to the problem of 5-coloring of planar graphs.

[学科分类] 计算机科学（综合）