Talk:Dominating set problem

From Wikipedia, the free encyclopedia

You have new messages (last change).

The language of this page needs to be cleaned up, especially the section containing the reduction from vertex cover. I removed some minor spelling and grammatical errors, but amost the whole section needs to be rewritten. The content seems OK. DVanDyck 13:31, 13 September 2006 (UTC)

[edit] Disconnected graph

I'd appreciate if someone could explain why this is not a counter-example: a graph with two vertices, A and B, and no edge between them. There's a vertex cover of size 0, namely the empty set. The reduction described is idempotent on this graph (there are no edges, so no new vertices or edges are added). However, there is no dominating set of size 0; the smallest dominating set is {A,B}, i.e., of size 2. 76.182.204.23 05:16, 26 March 2007 (UTC)

Retrieved from "http://en.wikipedia.org../../../d/o/m/Talk%7EDominating_set_problem_6a71.html"