[問題] 一個關於演算法的問題

[bin90909 (Ben)]

 大家好, 最近在解一個有關圖學理論的問題, 描述如下:

 問題描述如下:

 給一圖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
推 hcsoso:就算沒有 weight, 這是所謂的 max. P_3 packing problem,
→ hcsoso:即使在平面圖上都是 NP-complete. 你的圖有特殊性質嗎?
推 hcsoso:用 local search 可以有 1/2-eps 的近似演算法.
→ hcsoso:可參考 "On Local Search for Weighted k -Set Packing",
→ hcsoso:by Esther M. Arkin and Refael Hassin.
推 hcsoso:另外, 可以注意到就算是亂挑也會是個 1/3 近似演算法,
→ hcsoso:因為每一條 path 最多破壞另外三條 paths.
→ bin90909:太強大了!! 感謝樓上的資訊!! 拜讀提供的那篇Paper中
→ bin90909:感謝h大提供資料, 剛剛被我煩還耐心解答, 真是謝謝了.