Post by Deleted on Oct 28, 2017 7:56:42 GMT -5
Hi,
A algorithm with polynomial time, which receives a graph G and returns the stable set SA(G) of G with the property:
alpha(G) - |SA(G)| <= k for a constant k in N.
Prove that A can be used for determining , in polynomial time, a stable set of maximum cardinal in a given graph.
I have tried by taking K+1 isomorphic copies of the graph and I have tried to extend the graph. But I get stuck at this point, can you give me some help?
Please help.
Thanks!
I didn't find the right solution from the Internet.
References www.dreamincode.net/forums/topic/398870-graph-problem/
best advertisements
A algorithm with polynomial time, which receives a graph G and returns the stable set SA(G) of G with the property:
alpha(G) - |SA(G)| <= k for a constant k in N.
Prove that A can be used for determining , in polynomial time, a stable set of maximum cardinal in a given graph.
I have tried by taking K+1 isomorphic copies of the graph and I have tried to extend the graph. But I get stuck at this point, can you give me some help?
Please help.
Thanks!
I didn't find the right solution from the Internet.
References www.dreamincode.net/forums/topic/398870-graph-problem/
best advertisements