Connected dominating set (CDS) has a wide range of applications in multihop wireless networks. The Minimum CDS problem has been studied extensively in multihop wireless networks with uniform communication ranges. However, in practice, the nodes may have different communication ranges either because of the heterogeneity of the nodes, or due to interference mitigation, or due to a chosen range assignment for energy conservation. In this paper, we present a greedy approximation algorithm for computing a Minimum CDS in multihop wireless networks with disparate communications ranges and prove that its approximation ratio is better than the best one known in the literature. Our analysis utilizes a tighter relation between the independence number and the connected domination number.

This paper addresses the joint selection and power assignment of a largest set of given links which can communicate successfully at the same time under the physical interference model in the duplex (i.e. bidirectional) mode. For the special setting in which all nodes have unlimited maximum transmission power, Halldorsson and Mitra [5] developed an approximation algorithm with a huge constant approximation bound. For the general setting in which all nodes have bounded maximum transmission power, the existence of constant approximation algorithm remains open. In this paper, we resolve this open problem by developing an approximation algorithm which not only works for the general setting of bounded maximum transmission power, but also has a much smaller constant approximation bound.

This paper studies maximum multiflow (MMF) and maximum concurrent multiflow (MCMF) in muliti-channel multi-radio multihop wireless networks under the 802.11 interference model or the protocol interference model. We introduce a fine-grained network representation of multi-channel multi-radio multihop wireless networks and present some essential topological properties of its associated conflict graph. By exploiting these properties, we develop practical polynomial approximation algorithms for MMF and MCMF with constant approximation bounds regardless of the number of channels and radios. Under the 802.11 interference model, their approximation bounds are at most 20 in general and at most 8 with uniform interference radii; under the protocol interference model, if the interference radius of each node is at least c times its communication radius, their approximation bounds are at most 2 (⌈π/ arcsin c-1/2c⌉ + 1). In addition, we also prove that if the number of channels is bounded by a constant (which is typical in practical networks), both MMF and MCMF admit a polynomial-time approximation scheme under the 802.11 interference model or under the protocol interference model with some additional mild conditions.

Link scheduling is a fundamental problem in multihop wireless networks because the capacities of the communication links in multihop wireless networks, rather than being fixed, vary with the underlying link schedule subject to the wireless interference constraint. The majority of algorithmic works on link scheduling in multihop wireless networks assume binary interference models such as the 802.11 interference model and the protocol interference model, which often put severe restrictions on interference constraints for practical applicability of the link schedules. On the other hand, while the physical interference model is much more realistic, the link scheduling problem under physical interference model is notoriously hard to resolve and been studied only recently by a few works. This paper conducts a full-scale algorithmic study of link scheduling for maximizing throughput capacity or minimizing the communication latency in multihop wireless networks under the physical interference model. We build a unified algorithmic framework and develop approximation algorithms for link scheduling with or without power control.

The capacity region of multihop wireless network is involved in many capacity optimization problems. However, the membership of the capacity region is NP-complete in general, and hence the direct application of capacity region is quite limited. As a compromise, we often substitute the capacity region with a polynomial approximate capacity subregion. In this paper, we construct polynomial ¿-approximate capacity subregions of multihop wireless network under either 802.11 interference model or protocol interference model in which all nodes have uniform communication radii normalized to one and uniform interference radii ¿ ¿ 1. The approximation factor ¿ decreases with ¿ in general and is smaller than the best-known ones in the literature. For example, ¿ = 3 when ¿ ¿ 2.2907 under the 802.11 interference model or when ¿ ¿ 4.2462 under the protocol interference model. Our construction exploits a nature of the wireless interference called strip-wise transitivity of independence discovered in this paper and utilize the independence polytopes of cocomparability graphs in a spatial-divide-conquer manner. We also apply these polynomial ¿-approximate capacity subregions to compute ¿-approximate solutions for maximum (concurrent) multiflows.

In this paper we study (interpret) the precise composability guarantee of the generalised universal composability (GUC) feasibility with global setups that was proposed in the recent paper Canetti et al. (2007) from the point of view of full universal composability (FUC), that is, composability with arbitrary protocols, which was the original security goal and motivation for UC. By observing a counter-intuitive phenomenon, we note that the GUC feasibility implicitly assumes that the adversary has limited access to arbitrary external protocols. We then clarify a general principle for achieving FUC security, and propose some approaches for fixing the GUC feasibility under the general principle. Finally, we discuss the relationship between GUC and FUC from both technical and philosophical points of view. This should be helpful in gaining a precise understanding of the GUC feasibility, and for preventing potential misinterpretations and/or misuses in practice.

In wireless ad hoc networks, greedy forward routing is a localized geographic routing algorithm in which one node discards a packet if none of its neighbors is closer to the destination of the packet than itself, or otherwise forwards the packet to the neighbor closest to the destination. If all nodes have the same transmission radii, the critical transmission radius for greedy forward routing is the smallest transmission radius which ensures packets can be delivered by greedy forward routing through any source-destination pair. In this paper, we study asymptotic critical transmission radii of randomly deployed wireless ad hoc networks. Assume network nodes are represented by a Poisson point process of density n over a unit-area convex compact region whose boundary curvature is bounded. We show that the ratio of critical transmission radii to radic (lnn/pin) is asymptotically almost surely equal to radic (1/ (2/3 - radic(3)/2pi)) ap 1.6.

Connected dominating set (CDS) has a wide range of applications in wireless ad hoc networks. A number of distributed algorithms for constructing a small CDS in wireless ad hoc networks have been proposed in the literature. The majority of these distributed algorithms follow a general two-phased approach. The first phase constructs a dominating set, and the second phase selects additional nodes to interconnect the nodes in the dominating set. In this paper, we prove that the approximation ratio of the two-phased algorithm in [10] is at most 7 1/3, improving upon the previous best-known approximation ratio of 7.6 due to [12]. We also propose a new two-phased approximation algorithm and prove that its approximation ratio is at most 6 7/18. Our analyses exploit an improved upper bound on the number independent points that can be packed in the neighborhood of a connected finite planar set.

Relative neighborhood graph (RNG) has been widely used in topology control and geographic routing in wireless ad hoc networks. Its maximum edge length is the minimum requirement on the maximum transmission radius by those applications of RNG. In this paper, we derive the precise asymptotic probability distribution of the maximum edge length of the RNG on a Poisson point process over a unit-area disk. Since the maximum RNG edge length is a lower bound on the critical transmission radius for greedy forward routing, our result also leads to an improved asymptotic almost sure lower bound on the critical transmission radius for greedy forward routing.

Consider a random wireless ad hoc network represented by a Poisson point process over a unit-area disk with mean n. Let σn denote its critical transmission radius for greedy forward routing, and βo = 1/ (2/3 -- √3/2π) ≈ 1.62. It was recently proved that for any constant ε > 0, it is asymptotically almost sure that (1 -- ε) √βo in n/πn ≤ σn ≤ (1 + ε) √βo in n/πn. In this paper, we obtain tighter asymptotic bounds on σn. Specifically, we prove that for any constant c, the asymptotic probability of σn ≤ √βo in n + c/πn is at least 1 -- ( 1/1/βo--1/3 -- βo/2) e -c and at most e -βo/2 e -- c. Consequently, for any positive sequence (εn : n ≥ 1) with εn = o(In n) and εn → ∞, it is asymptotically almost sure that √βo in n --εn/πn ≤ σn ≤ √βo in n + εn/πn. We also conjecture that for any constant c, the asymptotic probability of σn ≤ √βo 1n n + c/σn is exactly exp (--(1/1/βo--1/3 -- β;o/2) e --c).

Data aggregation is a fundamental yet time-consuming task in wireless sensor networks. We focus on the latency part of data aggregation. Previously, the data aggregation algorithm of least latency [1] has a latency bound of (Delta - 1)R, where Delta is the maximum degree and R is the network radius. Since both Delta andRcould be of the same order of the network size, this algorithm can still have a rather high latency. In this paper, we designed an algorithm based on maximal independent sets which has an latency bound of 23R+ Delta - 18. Here Delta contributes to an additive factor instead of a multiplicative one; thus our algorithm is nearly constant approximation and it has a significantly less latency bound than earlier algorithms especially when Delta is large.

We investigate the key management problem for broadcasting applications. Previous work showed that batch rekeying can be more cost-effective than individual rekeying. Under the assumption that every user has probability p of being replaced by a new user during a batch rekeying period, we study the structure of the optimal key trees. Constant bounds on both the branching degree and the subtree size at any internal node are established for the optimal tree. These limits are then utilized to give an $O(n)$ dynamic programming algorithm for constructing the optimal tree for n users and any fixed value of p. In particular, we show that when $p > 1 - 3^{-1/3} \thickapprox 0.307$, the optimal tree is an n-star, and when $p\leq 1 - 3^{-1/3}$, each nonroot internal node has a branching degree of at most 4. We also study the case when p tends to 0 and show that the optimal tree resembles a balanced ternary tree to varying degrees depending on certain number-theoretical properties of n.

Flooding is one of the most fundamental operations in mobile ad hoc networks. Traditional implementation of flooding suffers from the problems of excessive redundancy of messages, resource contention, and signal collision. This causes high protocol overhead and interference with the existing traffic in the networks. Some efficient flooding algorithms were proposed to avoid these problems. However, these algorithms either perform poorly in reducing redundant transmissions or require each node to maintain 2-hop (or more) neighbors information. In the paper, we study the sufficient and necessary condition of 100 percent deliverability for flooding schemes that are based on only 1-hop neighbors information. We further propose an efficient flooding algorithm that achieves the local optimality in two senses: 1) the number of forwarding nodes in each step is minimal and 2) the time complexity for computing forwarding nodes is the lowest, which is O(nlogn), where n is the number of neighbors of a node. Extensive simulations have been conducted and simulation results have shown the excellent performance of our algorithm

Abstract—Flooding is one of the most fundamental operations in mobile ad hoc networks. Traditional implementation of flooding suffers from the problems of excessive redundancy of messages, resource contention, and signal collision. This causes high protocol overhead and interference to the existing traffic in the networks. Some efficient flooding algorithms were proposed to avoid these problems. However, these algorithms either perform poorly in reducing redundant transmissions, or require each node to maintain 2-hop (or more) neighbors information. In the paper, we study the sufficient and necessary condition of 100% deliverability for flooding schemes that are based on only 1-hop neighbors information. We further propose an efficient flooding algorithm that achieves the local optimality in two senses: 1) the number of forwarding nodes in each step is the minimal; 2) the time complexity for computing forwarding nodes is the lowest,

Greedy forward routing (abbreviated by GFR)in wireless ad hoc networks is a localized geographic routing in which each node discards a packet if one of its neighbors is closer to the destination of the packet than itself, or otherwise forwards the packet to the neighbor closest to the destination of the packet. If all nodes have the same transmission radii, the critical transmission radius for GFR is the smallest transmission radius which ensures that packets can be delivered between any source-destination pairs. In this paper, we study the asymptotic critical transmission radius for GFR in randomly deployed wireless ad hoc networks. We assume that the network nodes are represented by a Poisson point process of density n over a convex compact region of u it area with bounded curvature.Let ß0 = 1/ (⅔√3 over 2π) ≈ 1.62. We show that √ß0 1n n over πn is asymptotically almost surely (abbreviated by a.a.s.) the threshold of the critical transmission radius for GFR.I other words,for ß > ß0 if the trasmission radius is √ß 1n n over πn, it is a.a.s. packets can be delivered between any source-destination pairs; for any ß < ß0 if the transmission radius is √ß 1n noverπn, it is a.a.s. packets can't be delivered between some source-destination pair.

We consider the problem of job scheduling on a variable voltage processor with d discrete voltage/speed levels. We give an algorithm which constructs a minimum energy schedule for n jobs in $O(d n\log n)$ time. Previous approaches solve this problem by first computing the optimal continuous solution in $O(n^3)$ time and then adjusting the speed to discrete levels. In our approach, the optimal discrete solution is characterized and computed directly from the inputs. We also show that $O(n\log n)$ time is required; hence the algorithm is optimal for fixed d.

A password-based key derivation function (KDF)-a function that derives cryptographic keys from a password-is necessary in many security applications. Like any password-based schemes, such KDFs are subject to key search attacks (often called dictionary attacks). Salt and iteration count are used in practice to significantly increase the workload of such attacks. These techniques have also been specified in widely adopted industry standards such as PKCS and IETF. Despite the importance and widespread usage, there has been no formal security analysis on existing constructions. In this correspondence, we propose a general security framework for password-based KDFs and introduce two security definitions each capturing a different attacking scenario. We study the most commonly used construction H/sup (c)/(p/spl par/s) and prove that the iteration count c, when fixed, does have an effect of stretching the password p by log/sub 2/c bits. We then analyze the two standardized KDFs in PKCS #5. We show that both are secure if the adversary cannot influence the parameters but subject to attacks otherwise. Finally, we propose a new password-based KDF that is provably secure even when the adversary has full control of the parameters.

The memory required to store the context model for a PPM-style compressor increases exponentially with the order of the model (i.e., length of context). It is a challenging research problem to find ways to reduce the memory requirement of a large context model without sacrificing its coding efficiency. In this paper, we focus on bi-level image coding and investigate context reduction by clustering: that is, contexts predicting similar probability distributions are grouped together to share a common entropy coder. We give an O(kn) algorithm for optimally grouping n contexts into k clusters so that the total loss in coding efficiency is minimized. Previously no algorithm was known for solving this problem. We demonstrate the effectiveness of clustering by implementing a two-level compression scheme. Experimental results on the CCITT test images show that, using the same amount of memory, our scheme achieves better compression than the two-level PPM method of A. Moffat (1991).

The shortest-superstring problem is to find a shortest possible string that contains every string in a given set as substrings. This problem has applications to data compression and DNA sequencing. Since the problem is NP-hard and MAX SNP-hard, approximation algorithms are of interest. We present a new algorithm which always finds a superstring that is at most 2.89 times as long as the shortest superstring. Our result improves the 3-approximation result of Blum et al.

The energy usage of computer systems is becoming an important consideration, especially for battery-operated systems. Various methods for reducing energy consumption have been investigated, both at the circuit level and at the operating systems level. In this paper, we propose a simple model of job scheduling aimed at capturing some key aspects of energy minimization. In this model, each job is to be executed between its arrival time and deadline by a single processor with variable speed, under the assumption that energy usage per unit time, P, is a convex function, of the processor speed s. We give an off-line algorithm that computes, for any set of jobs, a minimum-energy schedule. We then consider some on-line algorithms and their competitive performance for the power function P(s)=s/sup p/ where p/spl ges/2. It is shown that one natural heuristic, called the Average Rate heuristic, uses at most a constant times the minimum energy required. The analysis involves bounding the largest eigenvalue in matrices of a special type.

We describe a technique for building hash indices for a large dictionary of strings. This technique permits robust retrieval of strings from the dictionary even when the query pattern has a significant number of errors. This technique is closely related to the classical Turan problem for hypergraphs. We propose a general method of multi-index construction by generalizing certain Turan hypergraphs. We also develop an accompanying theory for analyzing such hashing schemes. The resulting algorithms have been implemented and can be applied to a wide variety of recognition and retrieval problems.>

The Shortest Superstring Problem is to find a shortest possible string that contains every string in a given set as substrings. This problem has applications to data compression and DNA sequencing. As the problem is NP-hard and MAX SNP-hard, approximation algorithms are of interest. We present a new algorithm which always finds a superstring that is at most 2.89 times as long as the shortest superstring. Our result improves the 3-approximation result of Blum, Jiang, Li, Tromp, and Yannakakis (1991).>

We consider schemes for recursively dividing a set of geometric objects by hyperplanes until all objects are separated. Such a binary partition is naturally considered as a binary tree where each internal node corresponds to a division and the leaves correspond to the resulting fragments of objects. The goal is to choose the hyperplanes properly so that the size of the binary partition, i.e., the number of resulting fragments of the objects, is minimized. We construct binary partitions of size Ο(n log n) for n edges in the plane, and of size Ο(n) if the edges are orthogonal. In three dimensions, we obtain binary partitions of size Ο(n2) for n planar facets, and prove a lower bound of Ω(n3/2). Two applications of efficient binary partitions are given. The first is an Ο(n2)-sized data structure for implementing a hidden-surface removal scheme of Fuchs, Kedem and Naylor [5]. The second application is in solid modelling: given a polyhedron described by its n faces, we show how to generate an Ο(n2)-sized CSG (constructive-solid-geometry) formula whose literals correspond to half-spaces supporting the faces of the polyhedron (see Peterson [9] and Dobkin et al. [3]). The best previous results for both of these problems were Ο(n3).

It is shown that, given a set S of n points in $R^3 $, one can always find three planes that form an eight-partition of S, that is, a partition where at most ${n / 8}$ points of S lie in each of the eight open regions. This theorem is used to define a data structure, called an octant tree, for representing any point set in $R^3 $. An octant tree for n points occupies $O(n)$ space and can be constructed in polynomial time. With this data structure and its refinements, efficient solutions to various range query problems in two and three dimensions can be obtained, including (1) half-space queries: find all points of S that lie to one side of any given plane; (2) polyhedron queries: find all points that lie inside (outside) any given polyhedron; and (3) circle queries in $R^2 $: for a planar set S, find all points that lie inside (outside) any given circle. The retrieval time for all these queries is $T(n) = O(n^\alpha + m)$, where $\alpha = 0.8988$ (or 0.8471 in case (3)), and m is the size of the output. This performance is the best currently known for linear-space data structures that can be deterministically constructed in polynomial time.

We consider clustering problems under two different optimization criteria. One is to minimize the maximum intracluster distance (diameter), and the other is to maximize the minimum intercluster distance. In particular, we present an algorithm which partitions a set S of n points in the plane into two subsets so that their larger diameter is minimized in time Ο(n log n) and space Ο(n). Another algorithm with the same bounds computes a k-partition of S for any k so that the minimum intercluster distance is maximized. In both instances it is first shown that an optimal parition is determined by either a maximum or minimum spanning tree of S.

An algorithm is presented for finding a maximum-weight spanning tree of a set of n points in the Euclidean plane, where the weight of an edge (pi, pj) equals the Euclidean distance between the points pi and pj. The algorithm runs in time Ο (n logn) and requires Ο (n) space. If the points are vertices of a convex polygon (given in order along the boundary), then our algorithm requires only a linear amount of time and space. These bounds are the best possible in the algebraic computation-tree model. We also establish various properties of maximum spanning trees that can be exploited to solve other geometric problems.

Geometric algorithms are usually designed with continuous parameters in mind. When the underlying geometric space is intrinsically discrete, as is the case for computer graphics problems, such algorithms are apt to give invalid solutions if properties of a finite-resolution space are not taken into account. In this paper we discuss an approach for transforming geometric concepts and algorithms from the continuous domain to the discrete domain. As an example we consider the discrete version of the problem of finding all intersections of a collection of line segments. We formulate criteria for a satisfactory solution to this problem, and design an interface between the continuous domain and the discrete domain which supports certain invariants. This interface enables us to obtain a satisfactory solution by using plane-sweep and a variant of the continued fraction algorithm.

It is shown that any bounded region in Ed can be divided into 2d subregions of equal volume in such a way that no hyperplane in Ed can intersect all 2d of the subregions. This theorem provides the basis of a data structure scheme for organizing n points in d dimensions. Under this scheme, a broad class of geometric queries in d dimensions, including many common problems in range search and optimization, can be solved in linear storage space and sublinear time.

The study of constructing reliable systems from unreliable components goes back to the work of von Neumann, and of Moore and Shannon. The present paper studies the use of redundancy to enhance reliability for sorting and related networks built from unreliable comparators. Two models of fault-tolerant networks are discussed. The first model patterns after the concept of error-correcting codes in information theory, and the other follows the stochastic criterion used by von Neumann and Moore–Shannon. It is shown, for example, that an additional $k(2n - 3)$ comparators are sufficient to render a sorting network reliable, provided that no more than k of its comparators may be faulty.

Let S be a set of n points in three-dimensional space. It is shown that one can always find three planes that divide S into eight open regions, of which no seven together contain more than a n points where a is a constant octant-tree, for representing any point set in 3-space. Efficient solutions to various data retrieval problems are readily available with this structure. For example, using octant-trees, one can answer in sublinear time T (n)

Let $\bar V_k (n)$ be the minimum average number of pairwise comparisons needed to find the kth largest of n numbers $(k \geqq 2)$, assuming that all $n!$ orderings are equally likely. D. W. Matula proved that, for some absolute constant c, $\bar V_k (n) - n \leqq ck\ln \ln n$ as $n \to \infty $. In the present paper, we show that there exists an absolute constant $c' > 0$ such that $\bar V_k (n) - n \geqq c'k\ln \ln n$ as $n \to \infty $, proving a conjecture of Matula.

The task of eliminating invisible parts when generating an image is one of the central problems in computer graphics. One approach achieves the desired obscuring effect by assigning priority numbers to the faces of an object. Image generation can be speeded up significantly in these priority schemes if priority information of the faces can be partly computed in advance, before a viewing position is specified. These observations were first made by Schumacker and are utilized to advantage in simulation applications. However, the priority calculations are usually done manually, for lack of an adequate theoretical understanding. In this paper we study the underlying mathematical structure of these priority orders, and present efficient algorithms for handling some special classes of geometrical configurations.

Given a collection of disjoint objects in the plane, we are interested in translating them by a common vector. If we have a primitive for translating one object at a time, then the order in which the objects can individually be translated is often geometrically constrained. In this paper we study the nature of these constraints and exhibit optimal algorithms for finding valid motion ordering for several different classes of objects. These algorithms find use in computer display applications.

Dynamic programming is one of several widely used problem-solving techniques in computer science and operation research. In applying this technique, one always seeks to find speed-up by taking advantage of special properties of the problem at hand. However, in the current state of art, ad hoc approaches for speeding up seem to be characteristic; few general criteria are known. In this paper we give a quadrangle inequality condition for rendering speed-up. This condition is easily checked, and can be applied to several apparently different problems. For example, it follows immediately from our general condition that the construction of optimal binary search trees may be speeded up from O(n3) steps to O(n2), a result that was first obtained by Knuth using a different and rather complicated argument.

ASSTRACT. In the all-pair shortest distance problem, one computes the matrix D = (du), where dq is the minimum weighted length of any path from vertex i to vertexj in a directed complete graph with a weight on each edge. In all the known algorithms, a shortest path p, ~ achieving di./is also implicitly computed. In fact, logs(f (n)) is an information-theoretic lower bound, wheref(n) is the total number of distinct patterns (Po) for n-vertex graphs. As f(n) potentially can be as large as 2":', it would appear possible that a nontrivial lower bound can be derived this way in the decision tree model. The characterization and enumeration of realizable patterns is studied, and it is shown thatf(n) < C "~. Thus no lower bound greater than Cn 2 can be derived from this approach. It is proved as a corollary that the Triangular polyhedron T ~"~, defined in E ¢~' ~ by d,j> 0 and the triangle inequalities d~j + dik> d,k, has at most C" ' faces of all dimensions, thus resolving an open question in a similar information bound approach to the shortest distance problem.

Let $M(m,n)$ be the minimum number of pairwise comparisons which will always suffice to merge two linearly ordered lists of lengths m and n. We prove that $M(m,m + d) = 2m + d - 1$ whenever $m \geqq 2d - 2$. This generalizes earlier results of Graham and Karp $(d = 1)$, Hwang and Lin $(d = 2,3)$, Knuth $(d = 4)$, and shows that the standard linear merging algorithm is optimal whenever $m \leqq n \leqq \lfloor 3m/2 \rfloor + 1$.

Let Vk (n) be the minimum average number of pairwise comparisons needed to find the k-th largest of n numbers (k≥2), assuming that all n! orderings are equally likely. D. W. Matula proved that, for some absolute constant c, Vk(n)- n ≤ ck log log n as n → ∞. In the present paper, we show that there exists an absolute constant c′ ≫ 0 such that Vk(n) - n ≥ c′k log log n as n → ∞, proving a conjecture by Matula.

Let M ( m, n ) be the minimum number or comparators needed in an ( m, n )-merging network. It is shown that M ( m, n ) ≥ n (lg( m + 1))/2, which implies that Batcher's merging networks are optimal up to a factor of 2 + ε for almost all values of m and n . The limit r m = lim n→∞ M ( m, n )/ n is determined to within 1. It is also proved that M (2, n ) = [3 n /2].