Cohen, NachshonNutov, Zeev2018-12-132018-12-132018-12-132018-12-0110.1016/j.jcss.2018.08.001https://infoscience.epfl.ch/handle/20.500.14299/152082WOS:000445978200003Let R be a finite set of terminals in a convex metric space (M, d). We give approximation algorithms for problems of finding a minimum size set S subset of M of additional points such that the unit-disc graph G[R boolean OR S] of R boolean OR S satisfies some connectivity properties. Let Delta be the maximum number of independent points in a unit ball. For the Steiner Tree with Minimum Number of Steiner Points problem we obtain approximation ratio 1 + In(Delta - 1) +epsilon, which in R-2 reduces to 1 + In 4 +epsilon < 2.3863 +epsilon; this improves the ratios [(Delta + 1)/2 ] + 1 +epsilon of [19] and 2.5 + epsilon of [7], respectively. For the Steiner Forest with Minimum Number of Steiner Points problem we give a simple Delta-approximation algorithm, improving the ratio 2(Delta - 1) of [21]. We also simplify the Delta-approximation of [4], when G[R boolean OR S] should be 2-connected. (C) 2018 Elsevier Inc. All rights reserved.Computer Science, Hardware & ArchitectureComputer Science, Theory & MethodsComputer Sciencewireless networksunit-disc graphsteiner treesteiner forest2-connectivityapproximation algorithmsconnectivity problemssensor networksalgorithmtext::journal::journal article::research article