Re: [igraph] maximum number of independent sets

[Gábor Csárdi]

Hi Harun,

this is an exponential algorithm, so yes, it takes a long time. Maybe
there is a better algorithm specifically for trees that you could
implement. A quick search gave me this:

@article{Jung1988227,
title = "Parallel algorithms for computing maximal independent sets in
trees and for updating minimum spanning trees",
journal = "Information Processing Letters",
volume = "27",
number = "5",
pages = "227 - 236",
year = "1988",
note = "",
issn = "0020-0190",
doi = "DOI: 10.1016/0020-0190(88)90084-1",
url = 
"http://www.sciencedirect.com/science/article/B6V0F-45D9TVW-29/2/a99a57e7acd1f2e1e13da05ef147185a";,
author = "Hermann Jung and Kurt Mehlhorn",
keywords = "Parallel algorithm",
keywords = "independent set",
keywords = "tree",
keywords = "spanning tree"
}

Best,
Gabor

On Thu, Nov 25, 2010 at 6:36 PM, harun pirim <address@hidden> wrote:
> Hi All,
> I know that it is linear time to find the maximum number of independent sets
> (MNOIS) in over a tree.
> I have a tree with around 3000 nodes. I want to find MNOIS.
> I tried independence.number(.), and independent.vertex.sets(.). Looks like
> takes a lot of time. Is there a way in R using igraph lib. to efficiently
> calculate the MNOIS or minimum vertex cover?
> Thank you,
> Harun Pirim
> Ph.D. Candidate
> Miss. State Univ.
> Ind. & Sys. Eng.
>
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM