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