A matrix method to hypergraph transversal and covering problems with application in simplifying Boolean functions
Min Meng, Jun‐e Feng, Xiuxian Li · 2016
This paper investigates the transversal and covering problems of hypergraphs via semi-tensor product of matrices. First, by the definitions of incidence matrix of hypergraph and characteristic logical vector of a vertex subset, one necessary and sufficient criterion is established for hypergraph transversal, based on which a new algorithm to find the minimum transversal is given for any hypergraph. Then, via properties between a hypergraph and its dual hypergraph, the covering problem can reduce to be transversal problem, and another algorithm for covering problem is presented. Finally, one illustrative example and application to simplification of Boolean functions are provided to show the effectiveness and applicability of the theoretical results.