[請益] The Maximal Independent Set Problem

[bleed1979 (十三)]

參考 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
推 DJWS:你給的那個參考應該是錯的  目前還沒有P-time演算法
→ DJWS:http://blog.sina.com.cn/s/blog_64675f540100rfo8.html
→ DJWS:這個不知行不行  最大獨立集/最大團是精典題型  資料滿好找
→ DJWS:http://rsujskf.blog32.fc2.com/blog-entry-1446.html  解法
→ bleed1979:http://codepad.org/RnS4AGFJ  改blog程式丟上去還是TLE
→ bleed1979:另外如果上面程式#define改0去跑參考的最後一個圖
→ bleed1979:450個點，跑5分鐘還不會有結果。 不過還是很感謝。
推 DJWS:我回文在下面了~
→ DJWS:另外 maximal是局部最大(greedy method) maximum才是全域最大
→ DJWS:標題下的不太正確  因為這題是求maximum而非maximal
→ bleed1979:我改一下。
推 manlike:他給的參考沒說是P-time演算法，只說是目前最有希望達成
推 manlike:在P-time解掉NPC的演算法 = =
推 manlike:所以這參考應該是對的 XD
推 DJWS:唔  那就是我搞錯了  抱歉 orz