Re: [Boost-users] [BGL]MAXIMUM INDEPENDENT SET

From: LoadCom (LoadCom_at_[hidden])
Date: 2007-11-13 21:38:54

Hello Doug£¬

I see. Thanks for your reply.

It seems to be known as a NP-C problem to compute
the independent sets with minimum number of sets.

It's equivalent to another problem/description that 
coloring a graph with a minimum number of colors.

I've already found a graph coloring algorithm in the 
boost lib, it works quite well, both in efficiency 
and the fact it's quite close to the optimization result.

Thanks.

------------------				 
Max
2007-11-14

-------------------------------------------------------------
·¢¼þÈË£ºDouglas Gregor
·¢ËÍÈÕÆÚ£º2007-11-14 10:23:09
ÊÕ¼þÈË£ºboost-users_at_[hidden]
³­ËÍ£º
Ö÷Ì⣺Re: [Boost-users] [BGL]MAXIMUM INDEPENDENT SET


On Nov 11, 2007, at 5:11 PM, LoadCom wrote:

> Hello,
>
> I want to know if there's a "MAXIMUM INDEPENDENT SET" algorithm in  
> the lib.

We do not have any algorithms that compute maximal independent sets;  
sorry!

        - Doug
_______________________________________________
Boost-users mailing list
Boost-users_at_[hidden]
http://lists.boost.org/mailman/listinfo.cgi/boost-users