典型文献
限制性多源点偏心距增广问题
文献摘要：
给定一个赋权图G=(V,E;w,c)以及图G的一个支撑子图G1=(V,E1),这里源点集合S={s1,s2,…,sk}C V,权重函数w:E→(R)+,费用函数c:E\E1→(Z)+和一个正整数B,本文考虑两类限制性多源点偏心距增广问题,具体叙述如下:(1)限制性多源点最小偏心距增广问题是要寻找一个边子集E2(∈)E\E1,满足约束条件c(E2)≤B,目标是使得子图G1∪E2上源点集S中顶点偏心距的最小值达到最小;(2)限制性多源点最大偏心距增广问题是要寻找一个边子集E2(∈)E\E1,满足约束条件c(E2)≤B,目标是使得子图G1∪E2上源点集S中顶点偏心距的最大值达到最小.本文设计了两个固定参数可解的常数近似算法来分别对上述两类问题进行求解.
文献关键词：
组合优化;偏心距;增广问题;参数复杂性;固定参数可解的近似算法
中图分类号：
作者姓名：
李建平;蔡力健;李陈筠然;潘鹏翔
作者机构：
云南大学数学与统计学院数学系,云南昆明650504;中国科学院数学与系统科学研究院应用数学所,北京100190
文献出处：
引用格式：
[1]李建平;蔡力健;李陈筠然;潘鹏翔-.限制性多源点偏心距增广问题)[J].运筹学学报,2022(01):60-68
A类：
增广问题,支撑子图,参数复杂性,固定参数可解的近似算法
B类：
限制性,源点,偏心距,赋权图,一个支,G1,E1,点集,s1,s2,sk,权重函数,费用函数,正整数,子集,E2,顶点,最小值,大偏心,组合优化
AB值：
0.235806
相似文献
机标中图分类号，由域田数据科技根据网络公开资料自动分析生成，仅供学习研究参考。
