Plans regarding hypergraphs transversals (in Maxima/Lisp)
More...
Go to the source code of this file.
Detailed Description
Plans regarding hypergraphs transversals (in Maxima/Lisp)
 Todo:
 Connections
 Todo:
 Organisation

Split Transversals/Transversals.mac into several files.

Perhaps Transversals/Basics.mac, Transversals/Minimal.mac, Transversals/Bounded.mac, and Transversals/Greedy.mac.
 Todo:
 The triangle of the three possibilities

The complementary problem is about maximal independent sets, the dual problem is about hyperedge coverings.

Likely these problems have each at least one natural algorithm, different from the translations of the others.

So we need to provide a general scheme for translations.
 Todo:
 ind_hg(G)

See Combinatorics/Hypergraphs/IndependentSets/plans/general.hpp.

The testfunction okltest_ind_hg should be a generic testfunction, applicable to any function for computing the hypergraph of (maximal) independent subsets (the "independence hypergraph").

So, as with transversals, we must distinguish between the (many) possible algorithms for ind_hg.

An alternative method for computing ind_hg is by direct construction:

Bottomup: Start with all independent subsets of size 0. Then for k=0, 1, ... take the sets of size k and consider all possibilities to a vertex, obtain so level k+1. Those which cannot be extended go to the final result, while otherwise the processed level is removed.

This algorithm is for example efficient for complete graphs.

Topdown: We start with the full vertexset at level n. Then for k = n,n1, ... all subsets which are independent are moved to the final result, while otherwise all possible (k1)subsets are formed, which makes level k1, and level k is removed.

This algorithm is efficient for hypergraphs with no hyperedges.

Of course, a question is whether independence hypergraphs are really on its own, or we should standardise all considerations by considering transversals? Just taking the edgewisecomplement is not a big step? But it's a step, and also the literature is different.
Definition in file general.hpp.