3.7.31. Bipartite matching

Figure 3.7.7. A bipartite graph and one of its bipartite matching

Denotes the fact that, for a given constraint, a bipartite matching algorithm can be used within its filtering algorithm. A bipartite matching is a subgraph that pairs every vertex of a bipartite graph with exactly one other vertex. A bipartite graph is a graph for which the set of vertices can be partitioned in two parts such that no two vertices in the same part are joined by an edge. PartΒ (A) of FigureΒ 3.7.7 shows a bipartite graph with a possible division of the vertices in black and white, while partΒ (B) depicts with a thick line a bipartite matching of this graph.