%0 Journal Article
%T 最大简单共享问题的快速近似算法
%A 李建？
%A 张韬？
%A 谢之易？
%A 朱洪？
%J 软件学报
%P 492-499
%D 2008
%X 介绍了一种基于复制结点的消除线路交叉的模型.该模型提出了一个优化问题,就是最小化结点复制的数量.同时提出一个自定义问题——"最大简单共享问题",并证明最小化结点复制的数量与最大共享问题是等价的.证明了最大简单共享问题是np-hard的,给出了一种简单的贪心算法,并证明该贪心算法的近似度为3.引入一个"最大互斥简单共享问题",该问题是最大简单共享问题的2-近似.将其转化为在一系列图上的完美匹配问题,使该问题可以在多项式时间内得到完美解决.最后,在最大互斥简单共享的基础上,用局部搜索的方法将近似度提高到12/7.
%K 近似算法
%K 线路交叉
%K 结点复制
%K np-难
%K 最大简单共享
%U http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=20080302&flag=1