限制性多源点偏心距增广问题
限制性多源点偏心距增广问题
复制标题
DOI：
10.15960/j.cnki.issn.1007-6093.2022.01.004
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
潘鹏翔
中科院分区：
文献类型：
--
作者：
李建平;蔡力健;李陈筠然;潘鹏翔
给定一个赋权图G= (V,E;w,c)以及图G的一个支撑子图G_1 = (V,E_1),这里源点集合S = {S_1,S_2, …,S_k} ⊆ V,权重函数w : E→ R~+,费用函数c :EE_1→ Z+和一个正整数B,本文考虑两类限制性多源点偏心距增广问题,具体叙述如下:(1)限制性多源点最小偏心距增广问题是要寻找一个边子集E_2 ⊆EE_1,满足约束条件c(E_2) ≤ B,目标是使得子图G_1 ∪E_2上源点集S中顶点偏心距的最小值达到最小;(2)限制性多源点最大偏心距增广问题是要寻找一个边子集E_2⊆ EE_1,满足约束条件c(E_2)≤B,目标是使得子图G_1∪E_2上源点集S中顶点偏心距的最大值达到最小。本文设计了两个固定参数可解的常数近似算法来分别对上述两类问题进行求解。