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:
- $v$ is in $V'$
- $v$ shares at least one edge with some vertex in $V'$
Any useful links or suggestions would be really helpful. Thanks in advance! Seb