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