Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Exact transversal hypergraphs and application to Boolean &mgr;-functions
Eiter T. Journal of Symbolic Computation17 (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?
yes
no
Other reviews under "Graph Theory": Date
Graphs and algorithms
Gondran M., Minoux M. (ed), Vajda S., John Wiley & Sons, Inc., New York, NY, 1984. Type: Book (9789780471103745)
Jan 1 1985
On graph rewritings
Raoult J. Theoretical Computer Science 32(1-2): 1-24, 1984. Type: Article
Sep 1 1985
Non-partitionable point sets
Avis D. Information Processing Letters 19(3): 125-129, 1984. Type: Article
Jul 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy