Operations Research Transactions >
2022 , Vol. 26 >Issue 1: 60 - 68
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2022.01.004
The constrained multi-sources eccentricity augmentation problems
Received date: 2021-05-06
Online published: 2022-03-14
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.
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
| 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. |
/
| 〈 |
|
〉 |