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