标题:A matrix method to hypergraph transversal and covering problems with application in simplifying Boolean functions
作者:Meng, Min ;Feng, Jun-E. ;Li, Xiuxian
作者机构:[Meng, Min ;Feng, Jun-E. ] School of Mathematics, Shandong University, Jinan; 250100, China;[Li, Xiuxian ] Department of Mechanical Engineering, Unive 更多
会议名称:35th Chinese Control Conference, CCC 2016
会议日期:27 July 2016 through 29 July 2016
来源:Chinese Control Conference, CCC
出版年:2016
卷:2016-August
页码:2772-2777
DOI:10.1109/ChiCC.2016.7553784
关键词:covering problem; semi-tensor product; simplifying Boolean function; transversal problem
摘要: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. © 2016 TCCT.
收录类别:EI;SCOPUS
资源类型:会议论文;期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-84987888629&doi=10.1109%2fChiCC.2016.7553784&partnerID=40&md5=4a888b8b7b9ead54b75e487104fca53a
TOP