作者bleed1979 (十三)
站内Prob_Solve
标题[请益] The Maximal Independent Set Problem
时间Sat Feb 25 10:36:44 2012
参考
http://www.dharwadker.org/independent_set/
并根据演算法实作自己的版本。
http://codepad.org/smRwl6MZ
http://pastie.org/3451941
测试题目是SPOJ3196
http://www.spoj.pl/problems/DIVREL/
目前仍是TLE。
想请教有没有更快的演算法，谢谢。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.25.249.107
1F：推 DJWS:你给的那个参考应该是错的 目前还没有P-time演算法 02/25 12:29
3F：→ DJWS:这个不知行不行 最大独立集/最大团是精典题型 资料满好找 02/25 13:10
6F：→ bleed1979:另外如果上面程式#define改0去跑参考的最後一个图 02/25 13:52
7F：→ bleed1979:450个点，跑5分钟还不会有结果。 不过还是很感谢。 02/25 13:52
8F：推 DJWS:我回文在下面了~ 02/25 14:06
9F：→ DJWS:另外 maximal是局部最大(greedy method) maximum才是全域最大 02/25 14:07
10F：→ DJWS:标题下的不太正确 因为这题是求maximum而非maximal 02/25 14:08
11F：→ bleed1979:我改一下。 02/25 14:16
12F：推 manlike:他给的参考没说是P-time演算法，只说是目前最有希望达成 02/28 01:15
13F：推 manlike:在P-time解掉NPC的演算法 = = 02/28 01:16
14F：推 manlike:所以这参考应该是对的 XD 02/28 01:19
15F：推 DJWS:唔 那就是我搞错了 抱歉 orz 02/28 13:05