Reducing the diameter of a unit disk graph via node addition

摘要

This paper addresses a hop-constrained graph design optimization problem which is related to efficiency and reliability issues of communication protocols in wireless networks. In particular, we study the problem of adding a minimum size set of points to a given unit disk graph in such a way that in the resulting graph any two original points have hop-distance at most a given bound D. After having proved the hardness of the problem, we propose two different bi-criteria algorithms that, conjunctively, provide logarithmic approximation ratio on both criteria. We remark that our first algorithm, while unable to provide any approximation guarantee in the general case, does yield an (O(1), O(1))-approximation for a wide set of instances. (C) 2015 Elsevier B.V. All rights reserved.