[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] largest independent vertex sets
From: |
yux1991 |
Subject: |
Re: [igraph] largest independent vertex sets |
Date: |
Wed, 17 Jul 2019 14:11:15 -0400 |
Hi Szabolcs,
Thank you for your reply. The lattice I am testing right now is quite small,
with about 200 vertices, which already take several minutes. The real case I
plan to run has about 10,000 vertices, so I guess it may not be reasonable to
keep them in memory.
Yu Xiang
-----Original Message-----
From: igraph-help <igraph-help-bounces+yux1991=address@hidden> On Behalf Of
Szabolcs Horvát
Sent: Wednesday, July 17, 2019 12:13 PM
To: Help for igraph users <address@hidden>
Subject: Re: [igraph] largest independent vertex sets
Hello Yu,
How big is your lattice? Is it reasonable to keep the complement graph in
memory?
Szabolcs
On Wed, 17 Jul 2019 at 15:46, <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
>
> Phone: (518) 833-4710
>
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help
_______________________________________________
igraph-help mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help