|November 11th, 2016, 01:25 PM||#1|
Joined: Nov 2016
Let A be a algorithm with polynomial time, which receives a graph G and returns the stable set SA(G) of G with the property:
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?
|Thread||Thread Starter||Forum||Replies||Last Post|
|A graph problem in graph theory!||lubna_mira||Applied Math||0||January 12th, 2014 02:52 PM|
|Graph problem.||FreaKariDunk||Calculus||5||May 31st, 2011 05:53 AM|
|can you help me with a graph problem, please?||saihat||Applied Math||0||March 10th, 2009 05:06 PM|
|Another Graph Problem||dajaka||Algebra||0||October 27th, 2008 09:12 AM|
|Graph Problem||dajaka||Algebra||0||October 27th, 2008 09:10 AM|