P
picker
Guest
picker Asks: Maximum matching for bipartite graph with category restriction.
The general maximum matching on bipartite graphs is extracted as follows: We have a bipartite graph G, which contains two sets of vertices without any connections within the two sets and several connections between the two sets. We want to find the maximum matching (number of connections) where there are no two selected edges connected to the same vertex.
Consider the following restriction. If the vertices on the left-hand side ${X}$ have one or several specific label, e.g., $x_1 = 1, x_2 = 2, x_3 = 2, x_4 = {1 and 3} ...$
If we want to achieve that, finally, the match has uniform label distribution. How can we design the algorithm to calculate the maximum matching number?
For example, we have two kinds of labels, 1 and 2. The final matching should have $\frac{k}{2}$ matchings with $label = 1$ and $\frac{k}{2}$ matchings with $label = 2$ if the final matching number is $k$.
The general maximum matching on bipartite graphs is extracted as follows: We have a bipartite graph G, which contains two sets of vertices without any connections within the two sets and several connections between the two sets. We want to find the maximum matching (number of connections) where there are no two selected edges connected to the same vertex.
Consider the following restriction. If the vertices on the left-hand side ${X}$ have one or several specific label, e.g., $x_1 = 1, x_2 = 2, x_3 = 2, x_4 = {1 and 3} ...$
If we want to achieve that, finally, the match has uniform label distribution. How can we design the algorithm to calculate the maximum matching number?
For example, we have two kinds of labels, 1 and 2. The final matching should have $\frac{k}{2}$ matchings with $label = 1$ and $\frac{k}{2}$ matchings with $label = 2$ if the final matching number is $k$.
SolveForum.com may not be responsible for the answers or solutions given to any question asked by the users. All Answers or responses are user generated answers and we do not have proof of its validity or correctness. Please vote for the answer that helped you in order to help others find out which is the most helpful answer. Questions labeled as solved may be solved or may not be solved depending on the type of question and the date posted for some posts may be scheduled to be deleted periodically. Do not hesitate to share your thoughts here to help others.