Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Exact transversal hypergraphs and application to Boolean -functions
Eiter T.  Journal of Symbolic Computation 17 (3): 215-225, 1994. Type: Article
Date Reviewed: Nov 26 2020

A hypergraph is a generalized structure of a graph in which an edge, called a hyperedge, can have more than two vertices. A subset T is said to be a transversal of a given hypergraph if it intersects every (non-empty) set of vertices in the hypergraph. A hypergraph is called an exact transversal hypergraph (xt-hypergraph) if every transversal of it is an exact transversal.

In the paper, Eiter first proposes an algorithm for xt-hypergraph recognition and establishes that recognizing xt-hypergraphs can be done in polynomial time with a runtime bounded by O(mS2), where m is the order of the hypergraph concerned and S is the input size. Following this, he proposes an algorithm to generate minimal transversals of a hypergraph and proves that the minimal traversals of an xt-hypergraph can be obtained in inverse lexicographic order with a delay of O(nS), and hence the maximal independent set can be obtained in lexicographic order with a delay of O(nS).

In the second half of the paper, the author describes some applications of the study to Boolean μ-functions. Let fE be a Boolean function corresponding to a monotone Boolean expression E in conjunctive normal form (CNF) or disjunctive normal form (DNF). The first theorem of the section states that deciding whether the function fE is μ-equivalent is possible in n2m3, where m is the number of clauses of E. It is also proved that deciding whether a Boolean function fE corresponding to a monotone Boolean expression E is a μ-function is co-NP-complete. As the final result of the paper, the author establishes that the prime implicants of the dual of an n-ary monotone μ-function f can be generated in lexicographic order with a delay of O(nS), provided the prime implicants of f are given.

The paper is written beautifully and the content is innovative and insightful.

Reviewer:  Sudev Naduvath Review #: CR147123 (2104-0082)
Bookmark and Share
Graph Theory (G.2.2 )
Computations On Polynomials (F.2.1 ... )
Would you recommend this review?
Other reviews under "Graph Theory": Date
Attention models in graphs: a survey
Lee J., Rossi R., Kim S., Ahmed N., Koh E.  ACM Transactions on Knowledge Discovery from Data 13(6): 1-25, 2019. Type: Article
Sep 20 2021
Recognizing weak embeddings of graphs
Akitaya H., Fulek R., Tóth C.  ACM Transactions on Algorithms 15(4): 1-27, 2019. Type: Article
Mar 12 2021
Graph theory and its applications (3rd ed.)
Gross J., Yellen J., Anderson M.,  Chapman&Hall/CRC, Boca Raton, FL, 2018. 591 pp. Type: Book (978-1-482249-48-4)
Oct 23 2019

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2021 ThinkLoud, Inc.
Terms of Use
| Privacy Policy