My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Reply
 
LinkBack Thread Tools Display Modes
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:
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?
boob96 is offline  
 
Reply

  My Math Forum > Science Forums > Computer Science

Tags
graph, problem



Thread Tools
Display Modes


Similar Threads
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





Copyright © 2017 My Math Forum. All rights reserved.