Re: [igraph] maximum number of independent sets

[Tamas Nepusz]

Hi Harun,

There's also a pseudo-code for finding a maximum independent set in a
tree here:

http://math.stackexchange.com/questions/8433/maximum-independent-set-in-a-tree-review-algorithm-need-proof

-- 
T.


On Fri, Nov 26, 2010 at 11:42:09AM +0100, Gábor Csárdi wrote:
> 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
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help