限制性多源点偏心距增广问题

给定一个赋权图$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$中顶点偏心距的最大值达到最小。本文设计了两个固定参数可解的常数近似算法来分别对上述两类问题进行求解。

The constrained multi-sources eccentricity augmentation problems

Given a weighted graph $G=(V, E; w, c)$ and a spanning subgraph $G_{1}=(V, E_{1})$ of $G$, where a set $S=\{s_{1}, s_{2}, \cdots, s_{k}\}$ of $k$ sources in $V$, a weight function $w: E\rightarrow \mathbb{R}^{+}$, a cost function $c: E\setminus E_{1}\rightarrow \mathbb{Z}^{+}$, and a positive integer $B$, we consider two kinds of the constrained multi-sources eccentricity augmentation problems as follows. (1) The constrained multi-sources minimum eccentricity augmentation problem (the CMS-Min-EA problem, for short) is asked to find a subset $E_{2}\subseteq E\setminus E_{1}$ with a constraint $c(E_{2})\leq B$, the objective is to minimize the minimum of the eccentricities of vertices of $S$ in the graph $G_{1}\cup E_{2}$, and (2) The constrained multi-sources maximum eccentricity augmentation problem (the CMS-Max-EA problem, for short) is asked to find a subset $E_{2}\subseteq E\setminus E_{1}$ with a constraint $c(E_{2})\leq B$, the objective is to minimize the maximum of the eccentricities of vertices of $S$ in the graph $G_{1}\cup E_{2}$. For the two problems mentioned-above, we design two fixed parameter tractable (FPT) constant-approximation algorithms to solve them, respectively.