|Subject:||[igraph] largest independent vertex sets|
|Date:||Wed, 17 Jul 2019 09:43:59 -0400|
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?
Dept. of Physics, Applied Physics & Astronomy
Rensselaer Polytechnic Institute
Jonsson-Rowland Science Center 2W19
Phone: (518) 833-4710
|[Prev in Thread]||Current Thread||[Next in Thread]|