排序方式： 共有2条查询结果，搜索用时 78 毫秒
1
1.
给定一个赋权图$G=（V,E;w,c）$以及图$G$的一个支撑子图$G_{1}=（V,E_{1}）$,这里源点集合$S=\{s_{1},s_{2},\cdots,s_{k}\}\subseteq V$,权重函数$w：E\rightarrow\mathbb{R}^{+}$,费用函数$c：E\setminus E_{1}\rightarrow\mathbb{Z}^{+}$和一个正整数$B$,本文考虑两类限制性多源点偏心距增广问题,具体叙述如下：（1）限制性多源点最小偏心距增广问题是要寻找一个边子集$E_{2}\subseteq E\setminus E_{1}$,满足约束条件$c（E_{2}）$$\leq$$B$,目标是使得子图$G_{1}\cup E_{2}$上源点集$S$中顶点偏心距的最小值达到最小;（2）限制性多源点最大偏心距增广问题是要寻找一个边子集$E_{2}\subseteq E\setminus E_{1}$,满足约束条件$c（E_{2}）$$\leq$$B$,目标是使得子图$G_{1}\cup E_{2}$上源点集$S$中顶点偏心距的最大值达到最小。本文设计了两个固定参数可解的常数近似算法来分别对上述两类问题进行求解。 相似文献
2.
给定一个赋权图$G=（V,E;w,c）$以及图$G$的一个支撑子图$G_{1}=（V,E_{1}）$,这里源点集合$S=\{s_{1},s_{2},\cdots,s_{k}\}\subseteq V$,权重函数$w：E\rightarrow\mathbb{R}^{+}$,费用函数$c：E\setminus E_{1}\rightarrow\mathbb{Z}^{+}$和一个正整数$B$,本文考虑两类限制性多源点偏心距增广问题,具体叙述如下：（1）限制性多源点最小偏心距增广问题是要寻找一个边子集$E_{2}\subseteq E\setminus E_{1}$,满足约束条件$c（E_{2}）$$\leq$$B$,目标是使得子图$G_{1}\cup E_{2}$上源点集$S$中顶点偏心距的最小值达到最小;（2）限制性多源点最大偏心距增广问题是要寻找一个边子集$E_{2}\subseteq E\setminus E_{1}$,满足约束条件$c（E_{2}）$$\leq$$B$,目标是使得子图$G_{1}\cup E_{2}$上源点集$S$中顶点偏心距的最大值达到最小。本文设计了两个固定参数可解的常数近似算法来分别对上述两类问题进行求解。 相似文献
1