We consider a well studied generalization of the maximum clique problem which is defined as follows. Given a graph G on n vertices and an integer d >= 1, in the maximum diameter-bounded subgraph problem (MaxDBS for short), the goal is to find a (vertex) maximum subgraph of G of diameter at most d. For d=1, this problem is equivalent to the maximum clique problem and thus it is NP-hard to approximate it within a factor n^{1-epsilon}, for any epsilon > 0. Moreover, it is known that, for any d >= 2, it is NP-hard to approximate MaxDBS within a factor n^{1/2 - epsilon}, for any epsilon > 0. In this paper we focus on MaxDBS for the class of unit disk graphs. We provide a polynomial-time constant-factor approximation algorithm for the problem. The approximation ratio of our algorithm does not depend on the diameter d. Even though the algorithm itself is simple, its analysis is rather involved. We combine tools from the theory of hypergraphs with bounded VC-dimension, k-quasi planar graphs, fractional Helly theorems and several geometric properties of unit disk graphs.

In this paper, we study strategies for allocating and managing friendly jammers, so as to create virtual barriers that would prevent hostile eavesdroppers from tapping sensitive wireless communication. Our scheme precludes the use of any encryption technique. Applications include domains such as (i) protecting the privacy of storage locations where RFID tags are used for item identification, (ii) secure reading of RFID tags embedded in credit cards, (iii) protecting data transmitted through wireless networks, sensor networks, etc. By carefully managing jammers to produce noise, we show how to reduce the SINR of eavesdroppers to below a threshold for successful reception, without jeopardizing network performance.

Given two sets in the plane, R of n (terminal) points and S of m (Steiner) points, a full Steiner tree is a Steiner tree in which all points of R are leaves. In the bottleneck full Steiner tree (BFST) problem, one has to find a full Steiner tree T (with any number of Steiner points from S), such that the length of the longest edge in T is minimized, and, in the k-BFST problem, has to find a full Steiner tree T with at most k ≤ m Steiner points from S such that the length of the longest edge in T is minimized. The problems are motivated by wireless network design. In this paper, we present an exact algorithm of O((n+m)log2m) time to solve the BFST problem. Moreover, we show that the k-BFST problem is NP-hard and that there exists a polynomial-time approximation algorithm for the problem with performance ratio 4.

We consider a geometric optimization problem that arises in network design. Given a set P of n points in the plane, source and destination points s,t ∈ P, and an integer k > 0, one has to locate k Steiner points, such that the length of the longest edge of a bottleneck path between s and t is minimized. In this paper, we present an O(n log2 n)-time algorithm that computes an optimal solution, for any constant k. This problem was previously studied by Hou et al. [Hou10], who gave an O(n2log n)-time algorithm. We also study the dual version of the problem, where a value λ > 0 is given (instead of k), and the goal is to locate as few Steiner points as possible, so that the length of the longest edge of a bottleneck path between s and t is at most λ.

A power assignment is an assignment of transmission power to each of the nodes of a wireless network, so that the induced communication graph has some desired properties. The cost of a power assignment is the sum of the powers. The energy of a transmission path from node u to node v is the sum of the squares of the distances between adjacent nodes along the path. For a constant t > 1, an energy t-spanner is a graph G', such that for any two nodes u and v, there exists a path from u to v in G', whose energy is at most t times the energy of a minimum-energy path from a ton in the complete Euclidean graph. In this paper, we study the problem of finding a power assignment, such that (i) its induced communication graph is a 'good' energy spanner, and (ii) its cost is 'low'. We show that for any constant t > 1, one can find a power assignment, such that its induced communication graph is an energy t-spanner, and its cost is bounded by some constant times the cost of an optimal power assignment (where the sole requirement is strong connectivity of the induced communication graph). This is a very significant improvement over the best current result due to Shpungin and Segal, presented in last year's conference.