English

运筹学学报 ›› 2022, Vol. 26 ›› Issue (1): 60-68.doi: 10.15960/j.cnki.issn.1007-6093.2022.01.004

•   • 上一篇    下一篇

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

李建平1,*(), 蔡力健1, 李陈筠然2, 潘鹏翔1   

  1. 1. 云南大学数学与统计学院数学系, 云南昆明 650504
    2. 中国科学院数学与系统科学研究院应用数学所, 北京 100190
  • 收稿日期:2021-05-06 出版日期:2022-03-15 发布日期:2022-03-14
  • 通讯作者: 李建平 E-mail:jianping@ynu.edu.cn
  • 作者简介:李建平  E-mail: jianping@ynu.edu.cn
  • 基金资助:
    国家自然科学基金(11861075);国家自然科学基金(11461081);云南省创新团队（培育）项目(202005AE160006);云南省“云岭学者”人才建设项目，云南省科技厅和云南大学联合重点项目(2018FY001014);云南省高等学校创新研究团队项目(C176240111009)

The constrained multi-sources eccentricity augmentation problems

Jianping LI1,*(), Lijian CAI1, Junran LICHEN2, Pengxiang PAN1   

  1. 1. Department of Mathematics, School of Mathematics and Statistics, Yunnan University, Kunming 650504, Yunnan, China
    2. Institute of Applied Mathematics, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China
  • Received:2021-05-06 Online:2022-03-15 Published:2022-03-14
  • Contact: Jianping LI E-mail:jianping@ynu.edu.cn

RichHTML

14

PDF

177

摘要：

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

关键词: 组合优化, 偏心距, 增广问题, 参数复杂性, 固定参数可解的近似算法

Abstract:

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.

Key words: combinatorial optimization, eccentricity, augmentation problems, parameterized complexity, FPT approximation algorithms

中图分类号: