2
$\begingroup$

I'm a bit of a graph theory noob, so please forgive the absence of mathematical rigor in my question.

Here it is:

Given a graph $G \to (V,E)$, (where every vertex $v$ in $G$ has some weight $w$ associated to it), I am seeking an efficient algorithm that will find a subset $V'$ of the graph with the least total weight such that every vertex $v$ in $G$ satisfies at least one of the following conditions:

  1. $v$ is in $V'$
  2. $v$ shares at least one edge with some vertex in $V'$

Any useful links or suggestions would be really helpful. Thanks in advance! Seb

  • 0
    It's called a "minimum weighted [dominating set](http://en.wikipedia.org/wiki/Dominating_set)".2012-08-12

1 Answers 1