3.7.33. Bipartite matching
Figure 3.7.8. (A)Β A bipartite graph and (B)Β one of its bipartite matching
Denotes 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.8 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.
A used generalisation so called degree-matching of a graph is a spanning sugraph where every vertex is associated with the bound degree of the matched edges.