作者bin90909 (Ben)
看板Prob_Solve
標題[問題] 一個關於演算法的問題
時間Wed Jun 8 23:55:39 2011
大家好, 最近在解一個有關圖學理論的問題, 描述如下:
問題描述如下:
給一圖G(V,E) V為帶有一個整數權重的點, E為空集合.
要增加E, 有以下限制:
1. 每條路徑的長度必為2條edges, 且不形成circle
2. 每個Vertex只可交會0,1,2條edges
3. 每條路徑上的3個Vertices的權重合必>=0
求一組擁有最多條路徑的路徑分佈情形
簡單的說就是求一個有最多條路徑的路徑分布, 限制為每條路徑通
通都是三個vertices和兩條edges, 然後路徑上的vertices權重和要>=0
我找了一些graph theory的演算法, 像Matching, coloring, 但似乎解
決不了(或許可以, 我這方面知識較缺乏). 想請教大家有沒有推薦的
解決方向或是可以對應到一個已知的解決方法, 謝謝大家.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.5.201
1F：推 hcsoso:就算沒有 weight, 這是所謂的 max. P_3 packing problem, 06/09 00:14
2F：→ hcsoso:即使在平面圖上都是 NP-complete. 你的圖有特殊性質嗎? 06/09 00:15
3F：推 hcsoso:用 local search 可以有 1/2-eps 的近似演算法. 06/09 00:19
4F：→ hcsoso:可參考 "On Local Search for Weighted k -Set Packing", 06/09 00:20
5F：→ hcsoso:by Esther M. Arkin and Refael Hassin. 06/09 00:20
6F：推 hcsoso:另外, 可以注意到就算是亂挑也會是個 1/3 近似演算法, 06/09 00:26
7F：→ hcsoso:因為每一條 path 最多破壞另外三條 paths. 06/09 00:27
8F：→ bin90909:太強大了!! 感謝樓上的資訊!! 拜讀提供的那篇Paper中 06/09 00:29
9F：→ bin90909:感謝h大提供資料, 剛剛被我煩還耐心解答, 真是謝謝了. 06/09 01:12