Search

In this paper we propose a generalized Roman domination problem called connected strong k-Roman dominating set problem. It is NP-hard even in a unit ball graph. Unit ball graphs are the intersection graphs of equal sized balls in the three-dimensional space, they are widely used as a mathematical model for wireless sensor networks and some problems in computational geometry. This paper presents the first constant approximation algorithm with a guaranteed performance ratio at most 6 (k + 2) in unit ball graphs, where k is a positive integer. [ABSTRACT FROM AUTHOR]

Spectrum allocation is a difficult and hot issue in wireless ad hoc networks. An efficient method of spectrum allocation is a key factor to improve quality of service and performance of wireless networks. In this paper, we consider the spectrum allocation problem which asks how to allocate the least number of spectrum blocks in a field to ensure the service on any random k locations simultaneously. Our solution to the spectrum allocation problem is the minimum k-Roman dominating set. We propose two distributed algorithms for the issue of spectrum allocation in wireless ad hoc networks. One is a distributed 6 k-approximation algorithm for the spectrum allocation of satisfying any random k ( k ≥ 2) locations in the class of unit ball graphs. The other one is a better distributed algorithm for finding a (1 + ε)-approximation for the spectrum allocation problem of serving any random two locations, in the class of growth-bounded graphs. We also describe the simulation results and analyze them. [ABSTRACT FROM AUTHOR]