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

作     者：杨惠娟 YANG Hui-juan

作者机构：昭通学院数学与统计学院云南昭通657000 

基　　金：云南省教育厅科学研究项目“H-矩阵的几类子矩阵逆的无穷范数上界的估计研究”(2019J0910) 

出 版 物：《数学的实践与认识》 (Mathematics in Practice and Theory)

年 卷 期：2022年第52卷第4期

页      码：238-244页

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

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

学科分类：07[理学] 070104[070104] 0701[理学-数学类] 

馆 藏 号：203111314...