树上限制性k-node multi-multiway cut问题的近似算法

k-node multi-multiway cut问题作为multicut问题和multiway cut问题的推广问题是NP难的。首先,将k-严格顶点覆盖归约到此问题说明该问题与k-严格顶点覆盖具有同样的近似值。其次,运用贪婪策略设计了近似值为k的算法。最后,运用线性规划的LP-rounding技术改进算法得到近似值为min{2(q-k+1),k}的多项式时间算法。

一般图上的限制性k node multi-multiway cut问题的启发式算法

限制性k node multi-multiway cut问题作为multiway cut问题的自然推广是NP难的。论文研究了一般图上的限制k node multi-multiway cut问题,首先用LP-relaxation和LP-rounding技术确定至少断开的k个终端集合,其次用改进的域增长技术将求得的分数解调整为整数解从而设计了该问题的一个启发式算法。