Re: [igraph] largest independent vertex sets

[yux1991]

Hi Serafeim,

 

Thank you for your reply. However, that’s not what I need. First, I am
looking for the largest independent set, which is not necessarily the
maximal independent set. Second, “maximal_independent_vertex_sets()” outputs
a longer list than the “largest_independent_vertex_sets()”, which takes even
longer computation time. Maybe I did not make myself clear, but I just need
one tuple representing the largest independent set instead of a list of
tuples in the output. Do you know how to deal with it?

 

Best regards,

 

Yu Xiang

 

From: igraph-help <igraph-help-bounces+yux1991=address@hidden> On
Behalf Of serafim loukas
Sent: Wednesday, July 17, 2019 9:51 AM
To: Help for igraph users <address@hidden>
Subject: Re: [igraph] largest independent vertex sets

 

Hi,


I believe you need another function. 


If you need only the maximal independent vertex set use
“maximal_independent_vertex_sets()”  function.
https://igraph.org/python/doc/igraph.GraphBase-class.html#maximal_independe
nt_vertex_sets

Bests,

Serafeim







On 17 Jul 2019, at 15:43, address@hidden <mailto:address@hidden>
wrote:

Hi,
 
I am trying to find out a largest independent vertex set for a graph that
represents a randomly generated crystal lattice, then I came across igraph.
My program is written with Python. I managed to get a list of the largest
independent vertex sets using the largest_independent_vertex_sets() method
of the Graph class. However, that’s not quite what I want. All I need is
just a single largest independent vertex set, instead of a list of all
possibilities. There are thousands of vertices in my graph, therefore it
takes a very long time to calculate the complete list. I know it is a
NP-complete problem, but I think generating just one such set instead of
generating the complete list and then taking one from it would cut down the
runtime significantly. I looked at the source code written in C but was kind
of getting lost there. I am not sure whether this can be easily done by
modifying the source code. Could anybody help me with this issue? 
 
Best regards,
 
Yu Xiang
PhD Candidate
Dept. of Physics, Applied Physics & Astronomy 
Rensselaer Polytechnic Institute
Jonsson-Rowland Science Center 2W19
Email: address@hidden <mailto:address@hidden> 
Phone: (518) 833-4710
 
_______________________________________________
igraph-help mailing list
address@hidden <mailto:address@hidden> 
https://lists.nongnu.org/mailman/listinfo/igraph-help

<<attachment: winmail.dat>>