Search

Abstract: In this paper, two variations of the minimum cost homogeneous range assignment problem for 2-hop broadcast from a given source are considered. A set of radio stations are pre-placed in , and a source station (say) is marked. In our first problem, the objective is to find a real number r such that 2-hop homogeneous broadcast from is possible with range r, and the total power consumption of the entire network is minimum. In the second problem, a real number r is given and the objective is to identify the smallest subset of S for which range r can be assigned to accomplish the 2-hop broadcast from , provided such an assignment is possible. The first problem is solved in time and space. For the second problem, a 2-factor approximation algorithm is proposed that runs in time and space. [Copyright &y& Elsevier]

Given a set of n colored points in IR2 with a total of m (3 ≤ m ≤ n) colors, the problem of identifying the smallest color-spanning object of some predefined shape is studied in this paper. We shall consider two different shapes: (i) corridor and (ii) rectangle of arbitrary orientation. Our proposed algorithm for identifying the smallest color-spanning corridor is simple and runs in O(n2log n) time using O(n) space. A dynamic version of the problem is also studied, where new points may be added, and the narrowest color-spanning corridor at any instance can be reported in O(mn(α(n))2log m) time. Our algorithm for identifying the smallest color-spanning rectangle of arbitrary orientation runs in O(n3log m) time and O(n) space. [ABSTRACT FROM AUTHOR]

Abstract: Given a polyhedral terrain with n vertices, the shortest monotone descent path problem deals with finding the shortest path between a pair of points, called source (s) and destination (t) such that the path is constrained to lie on the surface of the terrain, and for every pair of points and on the path, if then , where denotes the distance of p from s along the aforesaid path. This is posed as an open problem by Berg and Kreveld [M. de Berg, M. van Kreveld, Trekking in the Alps without freezing or getting tired, Algorithmica 18 (1997) 306–323]. We show that for some restricted classes of polyhedral terrain, the optimal path can be identified in polynomial time. [Copyright &y& Elsevier]

In the unbounded version of the range assignment problem for all-to-all communication in 1D, a set of n radio-stations are placed arbitrarily on a line; the objective is to assign ranges to these radio-stations such that each of them can communicate with the others (using at most n - 1 hops) and the total power consumption is minimum. A simple incremental algorithm for this problem is proposed which produces optimum solution in O(n3) time and O(n2) space. This is an improvement in the running time by a factor of n over the best known existing algorithm for the same problem. [ABSTRACT FROM AUTHOR]

Abstract: Given a set S of n radio-stations located on a d-dimensional space, a source node s and an integer h , the h-hop broadcast range assignment problem deals with assigning ranges to the members in S so that s can communicate with all other members in S in at most h-hops, and the total power consumption is minimum. The problem is known to be NP-hard for . We propose an time algorithm for the one dimensional version () of the problem. This is an improvement over the existing result on this problem by a factor of h [A.E.F. Clementi et al. The minimum broadcast range assignment problem on linear multi-hop wireless networks, Theoret. Comput. Sci. 299 (2003) 751–761]. [Copyright &y& Elsevier]

Given a convex polygon with n vertices, we study the problem of identifying a triangle with its smallest side as large as possible among all the triangles that can be drawn inside the polygon. We show that at least one of the vertices of such a triangle must coincide with a vertex of the polygon. We also propose an O (n 2) time algorithm to compute such a triangle inside the given convex polygon. [ABSTRACT FROM AUTHOR]