Plans for the general module on graphcomponents.
More...
Go to the source code of this file.
Detailed Description
Plans for the general module on graphcomponents.
 Todo:
 Reduction to the hypergraph transversal problem

For a graph G let Gamma(G) be the general hypergraph with E(Gamma(G)) = V(Gamma(G)) = V(G) and with the hyperedge associated to v in V(G) the set of neighbours of v in G (i.e., adjacent vertices).

And let Gamma_r(G) ("r" like "reflexive") be the variation, obtained from the reflexive version of G.

Now a strict dominating set for G is a transversal of Gamma(G), while a dominating set for G is a transversal of Gamma_r(G).

The constructions Gamma(G) and Gamma_r(G) are fundamental, and should be provided ("eager" and "lazy").

Then the general algorithms for the hypergraph transversal problem can all be applied.

Are there special algorithms, exploiting that Gamma(G) is square?
Definition in file general.hpp.