S.O.S. Mathematics CyberBoard

Your Resource for mathematics help on the web!
It is currently Sun, 1 Dec 2024 05:57:51 UTC

All times are UTC [ DST ]




Post new topic Reply to topic  [ 1 post ] 
Author Message
 Post subject: Graph Problem
PostPosted: Tue, 10 Jan 2017 11:38:46 UTC 
Offline
S.O.S. Newbie

Joined: Tue, 10 Jan 2017 11:31:20 UTC
Posts: 3
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) - |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?


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 1 post ] 

All times are UTC [ DST ]


Who is online

Users browsing this forum: No registered users


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  
cron
Contact Us | S.O.S. Mathematics Homepage
Privacy Statement | Search the "old" CyberBoard

users online during the last hour
Powered by phpBB © 2001, 2005-2017 phpBB Group.
Copyright © 1999-2017 MathMedics, LLC. All rights reserved.
Math Medics, LLC. - P.O. Box 12395 - El Paso TX 79913 - USA