(5 pts) In a graph G = (V,E), a dominating set is a subset of vertices...

Transcribed Image Text:

(5 pts) In a graph G = (V,E), a dominating set is a subset of vertices D CV such that every vertex NOT in D is adjacent to a vertex in D. Formulate a integer linear program to find the smallest size dominating set in a graph. (5 pts) In a graph G = (V,E), a dominating set is a subset of vertices D CV such that every vertex NOT in D is adjacent to a vertex in D. Formulate a integer linear program to find the smallest size dominating set in a graph.