Efficient Algorithms for Dualizing Large-Scale Hypergraphs

Details Efficient Algorithms for Dualizing Large-Scale Hypergraphs Efficient Algorithms for Dualizing Large-Scale Hypergraphs

2011-02-18

arxiv.org/abs/1102.3813v2

Computer Science

Data Structures and Algorithms

Scientific paper

A hypergraph ${\cal F}$ is a set family defined on vertex set $V$. The dual of ${\cal F}$ is the set of minimal subsets $H$ of $V$ such that $F\cap H \ne \emptyset$ for any $F\in {\cal F}$. The computation of the dual is equivalent to many problems, such as minimal hitting set enumeration of a subset family, minimal set cover enumeration, and the enumeration of hypergraph transversals. Although many algorithms have been proposed for solving the problem, to the best of our knowledge, none of them can work on large-scale input with a large number of output minimal hitting sets. This paper focuses on developing time- and space-efficient algorithms for solving the problem. We propose two new algorithms with new search methods, new pruning methods, and fast techniques for the minimality check. The computational experiments show that our algorithms are quite fast even for large-scale input for which existing algorithms do not terminate in a practical time.

Affiliated with

Also associated with

No associations

Rating

Efficient Algorithms for Dualizing Large-Scale Hypergraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient Algorithms for Dualizing Large-Scale Hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Algorithms for Dualizing Large-Scale Hypergraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-212682