1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Graph Theory - Max. Independent set algorithm

  1. Oct 24, 2013 #1
    Graph Theory -- Max. Independent set algorithm

    1. The problem statement, all variables and given/known data

    Design a polynomial time greedy algorithm to compute a maximum independent set for a graph. Explain the algorithm and compute T_w(n).


    2. Relevant equations



    3. The attempt at a solution

    My terse and informal Internet research indicates that a maximum independent set cannot be calculated in polynomial time. For example:
    http://en.wikipedia.org/wiki/Independent_set_(graph_theory)#Finding_maximum_independent_sets

    What could my teacher possibly want? Do I need to design an algorithm that nobody else to date has done? I guess not. I think I misunderstand the question. Can someone help me understand what he wants?

    Thank you
     
  2. jcsd
  3. Oct 25, 2013 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Maybe "maximum independent set" is not meant in that way, and you are supposed to find an algorithm that finds an independent set where no other vertices can be added (should be easy in n^2). Just a guess, I don't know how the problem statement is meant.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Graph Theory - Max. Independent set algorithm
  1. Graph theory (Replies: 0)

  2. Graph Theory (Replies: 2)

  3. Graph Theory (Replies: 0)

  4. Graph Theory (Replies: 4)

Loading...