OKlibrary  0.2.1.6
general.hpp File Reference

Plans for the general module on graph-components. More...

Go to the source code of this file.


Detailed Description

Plans for the general module on graph-components.

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.