Plans regarding notions of bicliques.
More...
Go to the source code of this file.
Detailed Description
Plans regarding notions of bicliques.
 Todo:
 The notion of a "biclique"

General discussion:

The "full" mathematical notion of a biclique B in a (general/multi) graph G is that of a subgraph of G, which itself is a complete bipartite graph.

Since the edges determine the subgraph B, it is natural to represent B by a set B' of edges.

However then we have the problem, that this notion is not stable under subsetformation, i.e., a subset of B' in general is not again a biclique.

So for multigraphs and graphs G alternatively we can use sets of *vertices* B' such that we can find edges in B' making it a complete biclique.

For graphs this is the subgraph induced by B'

However, then it is needed to specify the bipartitioning, since in general there are many ways that a set of vertices could form a biclique.

For multigraphs a biclique partition is a "numerical condition", which seems perfectly appropriate since multigraphs are close to combinatorial matrices.

Only for general graphs, where the edges have an identity, we need to know precisely which edges are part of the biclique.

So we could speak of a "subgraphbiclique", "edgesetbiclique" and "vertexsetbiclique" (where the latter is a pair of vertexsets).

For the ordered graph versions instead a vertexsets we have vertexlists, and their order must conform with the given total order; the abbreviation then is "ovbc".

DONE (since we need two subsets, it's not really a hypergraph) The vertexbicliques then form a hereditary hypergraph (vertices the vertices of the given graph; "hereditary" means that for every hyperedge also every subset is a hyperedge, where here we must exclude subsets of size 0 or 1).

DONE (solved by using pairs) Likely for (general) digraphs for a given vertexbiclique there are several possibilities to interprete it as a edgebiclique, but otherwise there should be no ambiguities.

A subgraphbiclique as well as an edgebiclique can be refined by specifying an associated vertexbiclique (which fixes the bipartitioning).
 Todo:
 Abbreviations

"bc" for "biclique".

Bicliques exist as "sbc", "ebc" and "vbc" (subgraphs, edgesets or vertexsets).

A test would be named e.g. "sbc_ogdg_p".
 Todo:
 Maximal biclique
Definition in file BasicNotions.hpp.