-
Chapter and Conference Paper
Improved Lower Bounds for Shoreline Search
Shoreline search is a natural and well-studied generalisation of the classical cow-path problem: k initially co-located unit speed agents are searching for a line (called shoreline) in 2 dimensional Euclidean spa...
-
Chapter and Conference Paper
Exploration of Time-Varying Connected Graphs with Silent Agents
Exploration is a fundamental task in mobile computing. We study the version where a group of cooperating agents is situated in a graph, and the task is to make sure that every vertex of the graph is visited by...
-
Chapter and Conference Paper
Searching for a Non-adversarial, Uncooperative Agent on a Cycle
Assume k robots are placed on a cycle–the perimeter of a unit (radius) disk–at a position of our choosing and can move on the cycle with maximum speed 1. A non-adversarial, uncooperative agent, called bus, is mov...
-
Chapter and Conference Paper
The Complexity of Paging Against a Probabilistic Adversary
We consider deterministic online algorithms for paging. The offline version of the paging problem, in which the whole input is given in advance, is known to be easily solvable. If the input is random, chosen a...
-
Chapter and Conference Paper
Improved Spanners in Networks with Symmetric Directional Antennas
Consider a set \(S\) of sensors in a plane, each equipped with a directional antenna of beamwidth \(\frac{\pi }{2}\) and radius ...
-
Chapter and Conference Paper
Optimal Sensor Networks for Area Monitoring Using Rotating and Beam Sensors
We consider the problem of monitoring the Euclidean plane using rotating sensors with detection sectors and beam sensors. We assume that intruders can appear anywhere at any time and move arbitrarily fast, and...
-
Chapter and Conference Paper
Leader Election in Extremely Unreliable Rings and Complete Networks
In this paper we investigate deterministic leader election under the simple threshold model of omission dynamic faults: The computation is performed in synchronous steps; if the algorithm sends m messages in one ...