作者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