-
Chapter and Conference Paper
Graph Exploration by Energy-Sharing Mobile Agents
We consider the problem of collective exploration of a known n-node edge-weighted graph by k mobile agents that have limited energy but are capable of energy transfers. The agents are initially placed at an arbit...
-
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
Weak Coverage of a Rectangular Barrier
Assume n wireless mobile sensors are initially dispersed in an ad hoc manner in a rectangular region. They are required to move to final locations so that they can detect any intruder crossing the region in a dir...
-
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
Survivability of Swarms of Bouncing Robots
Bouncing robots are mobile agents with limited sensing capabilities adjusting their movements upon collisions either with other robots or obstacles in the environment. They behave like elastic particles slidin...
-
Chapter and Conference Paper
Complexity of Barrier Coverage with Relocatable Sensors in the Plane
We consider several variations of the problems of covering a set of barriers (modeled as line segments) using sensors that can detect any intruder crossing any of the barriers. Sensors are initially located in...
-
Chapter and Conference Paper
Independent Set with Advice: The Impact of Graph Knowledge
We are interested in online graph problems where the knowledge of the underlying graph G (all arriving vertices are from G) has a profound impact on the size of the advice needed to solve the problem efficiently....
-
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
Approximating the Edge Length of 2-Edge Connected Planar Geometric Graphs on a Set of Points
Given a set P of n points in the plane, we solve the problems of constructing a geometric planar graph spanning P 1) of minimum degree 2, and 2) which is 2-edge connected, respectively, and has max edge length bo...
-
Chapter and Conference Paper
Robust Sensor Range for Constructing Strongly Connected Spanning Digraphs in UDGs
We study the following problem: Given a set of points in the plane and a positive integer k > 0, construct a geometric strongly connected spanning digraph of out-degree at most k and whose longest edge length is ...
-
Chapter and Conference Paper
Online Graph Exploration with Advice
We study the problem of exploring an unknown undirected graph with non-negative edge weights. Starting at a distinguished initial vertex s, an agent must visit every vertex of the graph and return to s. Upon visi...
-
Chapter and Conference Paper
Asynchronous Exploration of an Unknown Anonymous Dangerous Graph with O(1) Pebbles
We consider the a team of asynchronous agents that must explore an unknown graph in presence of a black hole, a node which destroys all incoming agents without leaving any observable trace. Communication is ac...
-
Chapter and Conference Paper
Routing in Carrier-Based Mobile Networks
The past years have seen an intense research effort directed at study of delay/disruption tolerant networks and related concepts (intermittently connected networks, opportunistic mobility networks). As a funda...
-
Chapter and Conference Paper
Black Hole Search in Directed Graphs
We consider the problem of cooperative network exploration by agents under the assumption that there is a harmful host present in the network that destroys the incoming agents without outside trace – the so-ca...
-
Chapter and Conference Paper
More Efficient Periodic Traversal in Anonymous Undirected Graphs
We consider the problem of periodic graph exploration in which a mobile entity with (at most) constant memory, an agent, has to visit all n nodes of an arbitrary undirected graph G in a periodic manner. Graphs ar...
-
Chapter and Conference Paper
Strong Connectivity in Sensor Networks with Given Number of Directional Antennae of Bounded Angle
Given a set S of n sensors in the plane we consider the problem of establishing an ad hoc network from these sensors using directional antennae. We prove that for each given integer 1 ≤ k ≤ 5 there is a strongly ...
-
Chapter and Conference Paper
How Much Information about the Future Is Needed?
We propose a new way of characterizing the complexity of online problems. Instead of measuring the degradation of output quality caused by the ignorance of the future we choose to quantify the amount of additi...