Timeline for Maximum bipartite graph (1,n) "matching"
Current License: CC BY-SA 2.5
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 18, 2010 at 14:32 | history | edited | Tony Huynh | CC BY-SA 2.5 |
added 230 characters in body
|
| Mar 17, 2010 at 22:23 | comment | added | Karussell | Thanks Tony for the perfect graph suggestion. I will take a look + think about this! | |
| Mar 17, 2010 at 20:50 | comment | added | Suresh Venkat | I think the OP already indicated that the problem is NP-complete (via a comment on SO). The question being asked is whether there are restrictions to solve the problem in poly time. | |
| Mar 17, 2010 at 19:22 | comment | added | Grigory Yaroslavtsev | This is surely equivalent to maximum-clique, because you should just construct a graph, in which vertices correspond to $N(a)$ for each $a$ and connect two vertices with an edge iff the corresponding subsets intersect. Now you need to solve maximum-clique in the complement graph. | |
| Mar 17, 2010 at 17:57 | history | answered | Tony Huynh | CC BY-SA 2.5 |