A Practical Fast Algorithm for Enumerating Minimal SetCoverings
Takeaki Uno · IPSJ SIG Notes · 2002
For a set family F defined on a grand set E, a subset of F covering all the elements of E is called a set covering. The enumeration problem of minimal set covering is equal to the enumeration problem of hypergraph dualization, minimal hitting sets, and other other many problems, and have been studied intensively. However, the existence of an output polynomial algorithm for this problem is still open. However, there proposed an algorithm whose average computation time on computational experiments for random generated instances is output polynomial. In this paper, we propose a practical fast algorithm obtained by improving this algorithm, and by computational experiments, show that the average computation time for randomly generated instances is O(|E|) per output, by computational experiments.