A bipartite checker for 3 specific graph family. Implementation is on C++ using LEDA library.
- Create a certifying algorithm to check the bilaterality of a given graph G = (V, E).
- Compare with the LEDA bipartite checker.
Graph family:
- Synthetic Graph nested square (nodes, edges) = (n, m) ∈ {(10000, 19996), (40000, 79996), (90000, 179996)}
- Cycle Graph (nodes, edges) = (n, m) ∈ {(10001, 10001), (400001, 40001), (90001, 90001)}
- Synthetic Graph of 4 levels k nodes, 2k edges between 2 levels.
k ∈ {(500), (1000), (1500)}.
requirements: Let nodes of level Li, 1 < i < 4. The 2k edges between two levels Li, Li+1, 1 < i < 3, created like this: first we choose k edges , 1 <= j <= k, next we choose a random node u of Li level and create the rest k edges , 1 <= j <= k. In the end, after the creation of edges between 2 levels, we create randomly two more edges: the first one between level L1 and leve L3, and the second one between level L2 and level L4. For the first(second) node choose randomly a node from u ∈ L1(u ∈ L2) and a node from v ∈ L3(v ∈ L4) and create the edge.