There is a classical algorithm for computing the transversal
hypergraph described in Berge's Hypergraphs, Combinatorics
of Finite Sets (North-Holland, Amsterdam, etc., 1989).
The algorithm itself dates back much further and has been
rediscovered for various applications.
We provide here an implementation of a slightly modified
version of this algorithm in MATLAB.
The modifications mainly consist of not generating unnecessary
edges and not checking if certain edges are contained in certain
other edges when that is necessarily not the case.
While the worst-case complexity of this algorithm is not known
(and not polynomial), it does appear to work well in practice.
The main bottleneck is culling supersets from generated
intermediate lists. For more details, please consult our paper
in which we investigate the use of this and other algorithms
in an application to metabolic networks. Please let me know if
you would like access to this paper.
MATLAB hypergraph transversal code
This code is copyrighted, but it is available for
non-commercial use free of charge under the GNU
General Public License.
This page maintained by
Last modified June 2nd, 2008.