search

takemaru / graphillion

Fast, lightweight graphset operation library
Other
463 stars 40 forks source link

implement bipartite_graphs() #56

Closed zaki-joho closed 6 months ago

zaki-joho commented 3 years ago

OddEdgeSubgraphs.h/.cc construct a ZDD that represents the set of subgraphs with odd edges. bipartite_graphs() constructs a DD with the followings steps.

  1. Z_1: construct a DD that represents the set of subgraphs with odd edges.
  2. Z_2: construct a DD that represents the set of odd cycles from Z_1.
  3. Z_3: construct a DD using non_superset() with Z_2.
  4. return Z_3.