Search

We consider the problem of computing a sequence of range minimum queries. We assume a sequence of commands that contains values and queries. Our goal is to quickly determine the minimum value that exists between the current position and a previous position i. Range minimum queries are used as a sub-routine of several algorithms, namely related to string processing. We propose a data structure that can process these command sequences. We obtain efficient results for several variations of the problem, in particular we obtain O (1) time per command for the offline version and O (α (n)) amortized time for the online version, where α (n) is the inverse Ackermann function and n the number of values in the sequence. This data structure also has very small space requirements, namely O (ℓ) where ℓ is the maximum number of active i positions. We implemented our data structure and show that it is competitive against existing alternatives. We obtain comparable processing time, in the nanosecond range, and much smaller space requirements. [ABSTRACT FROM AUTHOR]

Wireless sensor network (WSN) consists of small sized devices containing different sensors to monitor physical, environmental and medical conditions during surveillance of fields, parking, borders and any targeted areas. Mostly WSN is deployed in harsh environments where battery can't be changed or recharged easily, therefore, battery power should be used efficiently. Sensor nodes are randomly deployed in remote areas by using aero plane and as a result more than one sensor may be covering the same area. The main problem is that if these sensors become functional at the same time it results in the wastage of battery resources and reducing the network lifetime. This paper resolve this issue by identifying disjoint subsets of the sensors such that alternate nodes cover the whole target area at different ON–OFF intervals of time. We have proposed to adopt ant-colony optimization to find the disjoint subsets of deployed sensor nodes. We have explored the algorithms for sensor deployment, cover set initialization, field identification and allocation. Finally, the optimal disjoint set allocation mechanism is explored. We have simulated our work using NS 2.35 and results ensure the dominance of our scheme over preliminaries in terms of number of field identification, disjoint set allocation, processing time and energy consumption. [ABSTRACT FROM AUTHOR]

We study the calculation of the largest pairwise intersections in a given set family. We give combinatorial and algorithmic results both for the worst case and for set families where the frequencies of elements follow a power law, as words in texts typically do. The results can be used in faster preprocessing routines in a simple approach to multi-document summarization. [ABSTRACT FROM AUTHOR]

Abstract: The Union–Find data structure for maintaining disjoint sets is one of the best known and widespread data structures, in particular the version with constant-time Union and efficient Find. Recently, the question of how to handle deletions from the structure in an efficient manner has been taken up, first by Kaplan et al. (2002) and subsequently by Alstrup et al. (2005) . The latter work shows that it is possible to implement deletions in constant time, without affecting adversely the asymptotic complexity of other operations, even when this complexity is calculated as a function of the current size of the set. In this note we present a conceptual and technical simplification of the algorithm, which has the same theoretical efficiency, and is probably more attractive in practice. [ABSTRACT FROM AUTHOR]

The maximum subarray problem is to find the array portion that maximizes the sum of array elements in it. For K disjoint maximum subarrays, Ruzzo and Tompa gave an O(n) time solution for one-dimension. This solution is, however, difficult to extend to two-dimensions. While a trivial solution of O(Kn3) time is easily obtainable for a two-dimensional array of size n × n, little study has been undertaken to improve the time complexity. We first propose an O(n + K log K) time solution for one-dimension. This is asymptotically equivalent to Ruzzo and Tompa's when sorted order is needed. Based on this, we achieve O(n3 + Kn2log n) time for two-dimensions. This is cubic time when K ≤ n/log n. We also show that this upper bound does not exceed O(n3log n) for K > n, namely O(n3 + min(K,n) · n log n). [ABSTRACT FROM AUTHOR]

The level sets of a map are the sets of points with level above a given threshold. The connected components of the level sets, thanks to the inclusion relation, can be organized in a tree structure, that is called the component tree. This tree, under several variations, has been used in numerous applications. Various algorithms have been proposed in the literature for computing the component tree. The fastest ones (considering the worst-case complexity) have been proven to run in O(n ln(n)). In this paper, we propose a simple to implement quasi-linear algorithm for computing the component tree on symmetric graphs, based on Tarjan's union-find procedure. We also propose an algorithm that computes the n most significant lobes of a map. [ABSTRACT FROM AUTHOR]

One of the main design issues for a sensor network is conservation of energy available at each sensor node. To increase lifetime of a sensor network, we can organize the sensors into disjoint sets so that only one set is active at a time. The lifetime of the network increases proportionally to the number of disjoint sets. In general, sensors are randomly scattered in the monitored area, thus the number of disjoint sets is significantly smaller than in the ideal case. In this paper, we propose a way to increase the number of disjoint sets using mobile sensors. We organize sensors into disjoint sets using the heuristic proposed by Sljepcevic and Potkonjak, Power efficient organization of wireless sensor networks IEEE International Conference on Communications (ICC) 2001. Then, we rearrange mobile sensors that are not included in any set. The rearrangement process consists of two phases. In the first phase, we identify the fields that are not covered by any of the remaining sensors. Then we identify the locations from which mobile sensors could cover the fields. In the second phase, our proposed heuristic selects sensors to be rearranged and locations where they will move to. This selection is made by considering the coverage before and after a mobile sensor is moved. Our experiments show that we can effectively increase the number of disjoint set with a small number of mobile sensors rearranged. [ABSTRACT FROM AUTHOR]