最大简单共享问题的快速近似算法

• 作者: 张韬 朱洪 李建 谢之易
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 近似算法 线路交叉 结点复制 NP-难 最大简单共享
• 年，卷（期）: 2008,（3）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 492-499
• 页数: 8页
• 分类号: TP301
• 字数: 7286字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2008.00492

摘要

介绍了一种基于复制结点的消除线路交叉的模型.该模型提出了一个优化问题,就是最小化结点复制的数量.同时提出一个自定义问题--"最大简单共享问题",并证明最小化结点复制的数量与最大共享问题是等价的.证明了最大简单共享问题是NP-hard的,给出了一种简单的贪心算法,并证明该贪心算法的近似度为3.线入一个"最大互斥简单共享问题",该问题是最大简单共享问题的2-近似.将其转化为在一系列图上的完美匹配问题,使该问题可以在多项式时间内得到完美解决.最后,在最大互斥简单共享的基础上,用局部搜索的方法将近似度提高到12/7.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	朱洪	复旦大学计算机科学与工程系	29	159	7.0	12.0
2	李建	复旦大学计算机科学与工程系	5	20	3.0	4.0
3	张韬	复旦大学计算机科学与工程系	3	3	1.0	1.0
4	谢之易	复旦大学计算机科学与工程系	2	7	1.0	2.0