The Reduction-Buildup Algorithm (RBA) for Efficient Support Set Construction

Philippine Information Technology Journal

Garnica, Unaiza M.¹  Juayong, Richelle Ann B.¹  Adorna, Henry N.¹  Malinao, Jasmine A.¹ 

关键词: Support Set. Set Cover Problem. Reduction- Buildup Algorithm.;   

DOI  :  10.3860/pitj.v3i1.2717

学科分类：计算机科学（综合）

来源: Philippine Society of Information Technology Educators

【 摘 要 】

The Reduction-Buildup Algorithm (RBA) is introduced in this study to be able to generate a minimal support set for a given conflict-free binary 2−tagged data set S of n dimen- sions. A support set φ, where |φ| ≤ n, is a set of dimensions obtained from S which forms another conflict-free data set. Finding this set has been proven to be NP-complete in. Unlike previous literatures that have transformed the orig- inal data set into another form prior to deriving a minimal support set, RBA shows that such a set can still be achieved in a comparable running time and utilizing lesser computa- tion space even in the absence of this transformation.

【 授权许可】

Unknown