完全图上无限制性K Node Multicut问题的近似算法

作者：杨惠娟

来源：数学的实践与认识, 2022, 52(04): 238-244.

• 完全图
• 无限制性K Node Multicut问题
• 局部比率定理

Node Multicut问题是图论与组合优化的经典问题,无限制性node Multicut问题是它的一类子问题.而无限制性K node multicut问题是无限制性node multicut问题的进一步推广形式.主要研究了完全图上的无限制性k Node Multicut问题.首先将部分点覆盖问题(PVC)多项式时间内归约到此问题证明该问题是NP难的,其次利用完全图独有的性质将该问题转换成特殊的部分击中集合问题(Special Partial Hitting Set Problem)并运用递归的思想和局部比率定理设计了求解该问题的2近似算法.

• 单位
  昭通学院