Re: [Roll] do we need a dominating set?

[Michael Richardson <mcr at sandelman.ca>]

>>>>> "Philip" == Philip Levis <pal at cs.stanford.edu> writes:
    >>>>>>> "Pascal" == Pascal Thubert <(pthubert)"
    >>>>>>> <pthubert at cisco.com>> writes:

    Pascal> A dominating set is a connected set of routers that enables
    Pascal> connectivity for all, that is all nodes in the network is
    Pascal> connected to at least one member of the dominating set.

    >> So, in a straight tree arrangement, the dominating set is the
    >> non-leaf nodes.  In a linear arrangement, the dominating set is
    >> all the nodes, except for the last one.  Is this correct?

    Philip> No. Unfortunately, that's not the definition of a dominating
    Philip> set.  Dominating set is a precise term that's been used for
    Philip> decades in graph algorithms. It helps to not try to redefine
    Philip> such terms, as all it does is lead to confusion.

    Philip> Here's the wikipedia page for dominating set:

    Philip> http://en.wikipedia.org/wiki/Dominating_set

  So my examples are correct interpretations of Pascal's definition, but
what we've defined does not go by that term. :-)

-- 
]       He who is tired of Weird Al is tired of life!           |  firewalls  [
]   Michael Richardson, Sandelman Software Works, Ottawa, ON    |net architect[
] mcr at sandelman.ottawa.on.ca http://www.sandelman.ottawa.on.ca/ |device driver[
   Kyoto Plus: watch the video <http://www.youtube.com/watch?v=kzx1ycLXQSE>
	               then sign the petition.