Author name cluster

Alan A. Bertossi

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

TCS Journal 2008 Journal Article

Efficient corona training protocols for sensor networks

Alan A. Bertossi
Stephan Olariu
Cristina M. Pinotti

Phenomenal advances in nano-technology and packaging have made it possible to develop miniaturized low-power devices that integrate sensing, special-purpose computing, and wireless communications capabilities. It is expected that these small devices, referred to as sensors, will be mass-produced and deployed, making their production cost negligible. Due to their small form factor and modest non-renewable energy budget, individual sensors are not expected to be GPS-enabled. Moreover, in most applications, exact geographic location is not necessary, and all that the individual sensors need is a coarse-grain location awareness. The task of acquiring such a coarse-grain location awareness is referred to as training. In this paper, two scalable energy-efficient training protocols are proposed for massively-deployed sensor networks, where sensors are initially anonymous and unaware of their location. The training protocols are lightweight and simple to implement; they are based on an intuitive coordinate system imposed onto the deployment area which partitions the anonymous sensors into clusters where data can be gathered from the environment and synthesized under local control.

Details DOI

TCS Journal 1990 Journal Article

String matching with weighted errors

Alan A. Bertossi
Fabrizio Luccio
Elena Lodi
Linda Pagli

In the approximate string matching problem, differences are allowed between the pattern string P and each of its occurrences in the text string T, and one is interested in finding all the occurrences of P in T with at most k differences. We consider here weighted differences (errors) between P and T and develop fast sequential and parallel algorithms. In particular, we allow the following types of errors: mismatch whose weight depends on the mismatching characters, extra character with constant weight, missing character with constant weight, and transposition of two consecutive characters with constant weight. A set of theoretical results allows to extend known algorithms to solve this problem with O(kn) sequential time and O(k + log m) parallel time on a 4PRAM model with max{n + k + 1, m p2} processors, where k is the maximum sum of the error weights, n is the length of T, and m is the length of P.

Details DOI