Re: [igraph] maximal.independent.vertex.sets

[Tamas Nepusz]

> Not sure if anyone here can answer this question, but is the notion  
> of a maximal independent vertex set as generated by  
> maximal.independent.vertex.sets(graph) in igraph the same as the  
> 'maximum independent set' as found in Vanetik, Shimony, and Gudes  
> paper
As I see, yes, it is the same. The concept of independent vertex set  
is fairly well-established in graph theory, it is practically a set of  
vertices that are not connected by a single edge at all. Note,  
however, that there is a difference between the _maximal_ independent  
vertex sets and the _largest_ (or _maximum_) independent vertex sets,  
the latter is a subset of the former. A maximal independent vertex set  
is an independent vertex set that is not contained by any other  
independent vertex set; a largest independent vertex set is a maximal  
independent vertex set such that no other independent vertex set  
contains more vertices. It is easy to select the largest independent  
vertex sets from the maximal ones, you simply have to keep only those  
that contain the most vertices.

--
Tamas