My Math Forum Graph Problem

 Computer Science Computer Science Forum

 November 11th, 2016, 01:25 PM #1 Newbie   Joined: Nov 2016 From: România Posts: 1 Thanks: 0 Graph Problem 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: $alpha(G) - \mid SA(G) \mid=<= 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?

 Tags graph, problem

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post lubna_mira Applied Math 0 January 12th, 2014 02:52 PM FreaKariDunk Calculus 5 May 31st, 2011 06:53 AM saihat Applied Math 0 March 10th, 2009 06:06 PM dajaka Algebra 0 October 27th, 2008 10:12 AM dajaka Algebra 0 October 27th, 2008 10:10 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top