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

The constrained multi-sources eccentricity augmentation problems

给定一个赋权图G=(V,E;w,c)以及图G的一个支撑子图G_(1)=(V,E_(1)),这里源点集合S={s_(1),s_(2),…,s_(k)}?V,权重函数w:E→R^(+),费用函数c:E\E_(1)→Z^(+)和一个正整数B,本文考虑两类限制性多源点偏心距增广问题,具体叙述如下:(1)限制性多源点最小偏心距增广问题是要寻找一个边子集E_(2)■E\E_(1),满足约束条件c(E_(2))≤B,目标是使得子图G_(1)∪E_(2)上源点集S中顶点偏心距的最小值达到最小;(2)限制性多源点最大偏心距增广问题是要寻找一个边子集E_(2)■E\E_(1),满足约束条件c(E_(2))≤B,目标是使得子图G_(1)∪E_(2)上源点集S中顶点偏心距的最大值达到最小。本文设计了两个固定参数可解的常数近似算法来分别对上述两类问题进行求解。

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),…,s_(k)}of k sources in V,a weight function w:E→R^(+),a cost function c:E E_(1)→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 CMSMin-EA problem,for short)is asked to find a subset E_(2)■E\E_(1) with a constraint c(E_(2))≤B,the objective is to minimize the minimum of the eccentricities of vertices of S in the graph G_(1)∪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)■E\E_(1) with a constraint c(E_(2))≤B,the objective is to minimize the maximum of the eccentricities of vertices of S in the graph G_(1)∪E_(2).For the two problems mentionedabove,we design two fixed parameter tractable(FPT)constant-approximation algorithms to solve them,respectively.