We don't disagree. It's just that that Wiki quote is not that useful in itself (in the sense that a minimum dominating set is not a maximum independent set (and vice versa), so a solution for one does not automatically give you a solution for the other). A reduction from independent set to dominating set is doable. I don't see a reduction in the other direction (after thinking about it for a minute or so). Do you know a reduction from dominating set to independent set (or vertex cover, whichever)?
On Feb 6, 6:00 am, "Rajiv Mathews" <[EMAIL PROTECTED]> wrote: > On Feb 6, 2008 5:42 AM, dor <[EMAIL PROTECTED]> wrote:> independent set). > Also, minimum dominating set and maximum independent > > set are not the same problem (they are not equivalent problems). You > > Again; I'll have to disagree. Of course they are not the same problem, > but they aren't the most incongruous. > > To quote the fastest resource I can lay my hands on: > :-)http://en.wikipedia.org/wiki/Dominating_set > "Dominating sets are closely related to independent sets: a maximal > independent set in a graph is necessarily a minimal dominating set." > > -- > Rajiv Mathews --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
