Answer to Question #43519 in Discrete Mathematics for Retta

Question #43519
I was wondering if anyone here could give me any pointers as to how to solve the following problem.

Let B=(L,R,E) be an undirected bipartite graph, ∀u∈L, ∃ s= {ei(u,wi)} ∈E; i=1,2.....n connect u to wi, where w∈R.

The problem is to find a minimum set K from L covering all R in B, K⊆L , ∑u∈K is minimal.

To clarify what I mean by covering: all vertices of R should should have at least one edge to any u∈K.

My intuition is that it's NP-Hard. If that is the case, any idea of what would be the best way to approximate the result (ie a minimum set K of L covering R) ?

Edit: Here is an example, consider the following bipartite graph: G={L∪R,E},
L={1,2,3,4,5,6},
R={A,B,C,D} ,
E={1A,1B,2A,2B,2C,3A,3C,4A,4B,4D,5A,5B,6A,6D}

And here is a covering minimum set will be {2,4}
0
Expert's answer

Answer in progress...

Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment

LATEST TUTORIALS
New on Blog
APPROVED BY CLIENTS