树上的限制性node multicut问题

摘要：

割集问题在图论和组合优化中占有重要地位，限制性node multicut问题是割集问题的一类比较重要的推广问题。树上的限制性node multicut问题是值得研究的一个问题。首先说明此问题是NP难的，其次用线性规划理论中的互补松弛条件设计了一个近似值2且时间复杂度为O(max{kn, n log n})的算法。并进一步说明了通过算法得到的解具有半整数的性质。

关键词：限制性node multicut、近似算法、互补松弛条件

分类号：O157.5(代数、数论、组合理论)

在线出版日期：2015-01-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：21-25