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 dominat
Yes, I agree. It is the minimum dominating set problem.
On Feb 6, 5:54 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
On Feb 6, 2008 4:54 AM, Rajiv Mathews <[EMAIL PROTECTED]> wrote:
> @Rupesh: Would you please elaborate or provide a reference to this
> "colorwave algorithm" you refer to. (On a lazy search) I couldn't find
> anything useful.
well, I was just trying to give brief hints on the problem type Robin
c
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 i
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
> might want to be a little more careful when defining classical
> problems -- if, for some reason,
The term colouring is a little confusing (is this a problem you wrote
yourself?). I suppose you mean: find a minimum cardinality set S such
that for each vertex v, either v is in S or at least one of v's
neighbours is in S. This problem is not equivalent to the maximum
independent set problem. It
Colorwave? This seems a rather obscure algorithm for maximum
independent set (that is, if it is actually an algorithm for the max
independent set). Also, minimum dominating set and maximum independent
set are not the same problem (they are not equivalent problems). You
might want to be a little mo
Robin,
You are use colorwave algorithm to solve the problem. In fact this
type of problem is call Minimum Connected Dominating Set or Minimum
Independent Set where no two adjacent vertices are filled with the
same color.
On Feb 5, 2008 1:04 AM, robin <[EMAIL PROTECTED]> wrote:
>
> Hello
>
> I
