Browse Prior Art Database

Minimal Disjoint Set Basis

IP.com Disclosure Number: IPCOM000088341D
Original Publication Date: 1977-May-01
Included in the Prior Art Database: 2005-Mar-04
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Cha, CW: AUTHOR [+4]

Abstract

Given a collection of finite sets, S = {S(1),S(2),...,S(1)} where 1 over mu over I = 1S={1,2, ... n}, a set basis Beta for S is defined as a collection of finite sets, Beta = {B(1), B(2),..., B(m)}, such that for each S(i) Epsilon S there exists a subset of Beta whose union equals S(1). Many practical problems [1,2] require one to find a minimal size set basis, Beta(min), for a given S. The problem is computationally difficult and is shown to be an NP-complete problem [4,5]. However, some applications require that one find a minimal size set basis whose elements are pairwise disjoint. For example [3], in macro deductive fault simulation, every input of the macro is associated with a set of faults that will invert the value of that input line.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

Minimal Disjoint Set Basis

Given a collection of finite sets, S = {S(1),S(2),...,S(1)} where 1 over mu over I = 1S={1,2, ... n}, a set basis Beta for S is defined as a collection of finite sets, Beta = {B(1), B(2),..., B(m)}, such that for each S(i) Epsilon S there exists a subset of Beta whose union equals S(1). Many practical problems [1,2] require one to find a minimal size set basis, Beta(min), for a given S. The problem is computationally difficult and is shown to be an NP-complete problem [4,5]. However, some applications require that one find a minimal size set basis whose elements are pairwise disjoint. For example [3], in macro deductive fault simulation, every input of the macro is associated with a set of faults that will invert the value of that input line. One may want to find the equivalence classes of these faults, such that any fault which belongs to one class cannot belong to another, i.e., to find the minimal size of disjoint set. This problem turns out to be solvable and the complexity of computation can be made linear to the entries of the fault lists.

An efficient algorithm is set forth below for finding the minimal size of the disjoint set basis for a given collection of finite sets. The complexity of computation is linearly proportional to the sum of the number of elements in the S(i)'s. Algorithm: Find the minimal disjoint set basis. Input: l lists S(1),S(2),...,S(l), the elements in S(i) are the elements in {1,2,...,n} , for all i. Output: lists M(1),M(2),...,M(m), the elements in M(j) are the elements in (1,2,...,n) , for all j. Each S(i) is the union of some M(j)'s. All M(j)'s are pairwise disjoint and m is minimal. Remarks: 1) The notation X <---- S(j) means remove one element from list S(j) and set X to the value of that element. 2) The program employs two- dimensional arrays C(u,v) and D(e,f) where 1 </- u </- n, 1 </- v </- 3, 1 </- e </- min{n,2/l/} = p and 1 </- f </- 3.

In general, arrays C a...