Computing minimal hitting set from first principles with RHS-tree
Lin Li · Microelectronics & Computer · 2002
In model-based diagnosis,there is widely used to compute the minimal hitting sets of conflict sets. There are HS-tree,HS-DAG,HST-tree,etc. but all of these methods are difficult to be programmed. This paper puts forward a new method to compute the minimal hitting sets by constructing balanced binary tree recursively,in brief,RHS-tree. The improvements of this algorithm are:1)It need recursive algorithm only and is easy to be programmed. 2)As a result of being pruned,the loss of the minimal hitting sets will not produce;3)When the new conflict sets are inserted,it is unnecessary to rebuild RHS-tree,instead,just adding the new branches to the RHS-tree. The comparison between RHS-tree and the others is given also.