3 Generalized matching Consider an undirected bipartite graph G = (VUU, E). We want to find...

Transcribed Image Text:

3 Generalized matching Consider an undirected bipartite graph G = (VUU, E). We want to find a maximum generalized matching M (subset of the edges E) between vertices in V and U, such that each vertex in v is matched to at most one vertex in U, and a vertex u in U is matched to at most dy vertices i V. For each node u in U, the upper bound d is given as part of the input. The example below shows an example of a generalized matching of size 5 (the upper bounds are written next to the vertices). V Give an algorithm to find a maximal generalized matching. U 2 2 3 3 Generalized matching Consider an undirected bipartite graph G = (VUU, E). We want to find a maximum generalized matching M (subset of the edges E) between vertices in V and U, such that each vertex in v is matched to at most one vertex in U, and a vertex u in U is matched to at most dy vertices i V. For each node u in U, the upper bound d is given as part of the input. The example below shows an example of a generalized matching of size 5 (the upper bounds are written next to the vertices). V Give an algorithm to find a maximal generalized matching. U 2 2 3

Answer rating: 100% (QA)

THEORY A Bipartite graph is a graph whose vertices is divided into two independent subsets U and Vsuch that every edge U V either connects a vertex fr... View the full answer