The constrained multi-sources eccentricity augmentation problems

Expand
  • 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 date: 2021-05-06

  Online published: 2022-03-14

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.

Cite this article

Jianping LI, Lijian CAI, Junran LICHEN, Pengxiang PAN . The constrained multi-sources eccentricity augmentation problems[J]. Operations Research Transactions, 2022 , 26(1) : 60 -68 . DOI: 10.15960/j.cnki.issn.1007-6093.2022.01.004

References

1 Bilò D , Gualà L , Proietti G . Improved approximability and non-approximability results for graph diameter decreasing problems[J]. Theoretical Computer Science, 2012, 417, 12- 22.
2 Demaine E D, Zadimoghaddam M. Minimizing the diameter of a network using shortcut edges[C]//Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 2010: 420-431.
3 Chung F R K . Diameters of graphs: Old problems and new results[J]. Congressus Numerantium, 1987, 16, 295- 317.
4 Frati F , Gaspers S , Gudmundsson J , et al. Augmenting graphs to minimize the diameter[J]. Algorithmica, 2015, 72 (4): 995- 1010.
5 Dodis Y, Khanna S. Designing networks with bounded pairwise distance[C]//Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), 1999: 750-759.
6 Schoone A A , Bodlaender H L , van Leeuwen J . Diameter increase caused by edge deletion[J]. Journal of Graph Theory, 1987, 11 (3): 409- 427.
7 Cygan M , Fomin F V , Kowalik ? , et al. Parameterized Algorithms[M]. New York: Springer, 2015.
8 Chepoi V , Vaxes Y . Augmenting trees to meet biconnectivity and diameter constraints[J]. Algorithmica, 2002, 33 (2): 243- 262.
9 Kapoor S , Sarwat M . Bounded-diameter minimum-cost graph problems[J]. Theory of Computing Systems, 2007, 41 (4): 779- 794.
10 Li C L , McCormick S T , Simchi-Levi D . On the minimum-cardinality-bounded-diameter and the bounded-cardinality-minimum-diameter edge addition problems[J]. Operations Research Letters, 1992, 11 (5): 303- 308.
11 Perumal S, Basu P, Guan Z. Minimizing eccentricity in composite networks via constrained edge additions[C]//Milcom IEEE Military Communications Conference, 2013.
12 Dyer M E , Frieze A M . A simple heuristic for the p-centre problem[J]. Operations Research Letters, 1985, 3 (6): 285- 288.
13 Hochbaum D S , Shmoys D B . A best possible heuristic for the k-center problem[J]. Mathematics of Operations Research, 1985, 10 (2): 180- 184.
Outlines

/