Skip to content

Minimal Hitting Set Solver with and without optimizations

Notifications You must be signed in to change notification settings

Edoar-do/MBASE-for-MHS-Problem

Repository files navigation

A minimal hitting set solver. Given a set M and a collection of its subsets, named N, we need to find all the minimal hitting sets. A hitting set (hs) is a subset of M such that its intersection with all the sets of N is non-empty. A minimal hitting set (mhs) is a hs such that it does not contain smaller hs

The problem in the application is formulated as follows:

A: boolean input matrix with |N| rows and |M| columns where $a_{ij}$ = 1 if $N_i$, the i_th set belonging to the collection N, has the j_th element of M (0 otherwise) MHS: output sequence of all the MHS found given the matrix A, generated in lexicographical order. Extra information: time required for computing the 'slow' version of the algorithm and the 'fast' one, in which some rows and cols are dropped in pre-processing

About

Minimal Hitting Set Solver with and without optimizations

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

 
 
 

Languages