Message Boards Message Boards

1 Reply
0 Total Likes
View groups...
Share this post:

maximal independent vertex set

Posted 10 years ago
Under "more information", in the MaximalIndependentVertexSet description (part of GraphUtilities) it says this function "gives an (approximate) maximal set of vertices such that no two vertices form an edge."

In what sense is it "approximate" ? I understand that finding a maximum independent set is hard, and one may want to approximate with a maximal set. But if I just want some maximal set, that should be easy to find without approximation.

In brief, how could the output of MaximalIndependentVertexSet fail to be a proper maximal independent set?
POSTED BY: Veit Elser
This article from MathWorld should be helpful (

I think it's probably bad wording. I think it's saying that a maximal set is an approximation of a maximum set. 
The article above states that it does return a maximal vertex set. 
POSTED BY: Sean Clarke
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract