In model-based diagnosis or other research fields, the hitting sets of a set cluster are usually used. In this paper we introduce some algorithms, including the new BHS-tree and Boolean algebraic algorithms. In the BHS-tree algorithm, a binary-tree is used for the computation of hitting sets, and in the Boolean algebraic algorithm, components are represented by Boolean variables. It runs just for one time to catch the minimal hitting sets. We implemented the algorithms and present empirical results in order to show their superiority over other algorithms for computing hitting sets.
Description
ScienceDirect - Information Processing Letters : The computation of hitting sets: Review and new algorithms
%0 Journal Article
%1 paper:lin:2003
%A Lin, Li
%A Jiang, Yunfei
%D 2003
%J Information Processing Letters
%K MBD MCS hitting-set
%N 4
%P 177 - 184
%R DOI: 10.1016/S0020-0190(02)00506-9
%T The computation of hitting sets: Review and new algorithms
%U http://www.sciencedirect.com/science/article/B6V0F-485XM64-1/2/e5a0081c9ff3ad30849c81751e7dc779
%V 86
%X In model-based diagnosis or other research fields, the hitting sets of a set cluster are usually used. In this paper we introduce some algorithms, including the new BHS-tree and Boolean algebraic algorithms. In the BHS-tree algorithm, a binary-tree is used for the computation of hitting sets, and in the Boolean algebraic algorithm, components are represented by Boolean variables. It runs just for one time to catch the minimal hitting sets. We implemented the algorithms and present empirical results in order to show their superiority over other algorithms for computing hitting sets.
@article{paper:lin:2003,
abstract = {In model-based diagnosis or other research fields, the hitting sets of a set cluster are usually used. In this paper we introduce some algorithms, including the new BHS-tree and Boolean algebraic algorithms. In the BHS-tree algorithm, a binary-tree is used for the computation of hitting sets, and in the Boolean algebraic algorithm, components are represented by Boolean variables. It runs just for one time to catch the minimal hitting sets. We implemented the algorithms and present empirical results in order to show their superiority over other algorithms for computing hitting sets.},
added-at = {2009-06-23T14:47:31.000+0200},
author = {Lin, Li and Jiang, Yunfei},
biburl = {https://www.bibsonomy.org/bibtex/2ada28ac5559d963062f7adbaaf2ad160/mschuber},
description = {ScienceDirect - Information Processing Letters : The computation of hitting sets: Review and new algorithms},
doi = {DOI: 10.1016/S0020-0190(02)00506-9},
interhash = {897f5f66353cec4003923d76588d1835},
intrahash = {ada28ac5559d963062f7adbaaf2ad160},
issn = {0020-0190},
journal = {Information Processing Letters},
keywords = {MBD MCS hitting-set},
number = 4,
pages = {177 - 184},
timestamp = {2009-06-23T14:47:31.000+0200},
title = {The computation of hitting sets: Review and new algorithms},
url = {http://www.sciencedirect.com/science/article/B6V0F-485XM64-1/2/e5a0081c9ff3ad30849c81751e7dc779},
volume = 86,
year = 2003
}