45 Result(s)
within
English
Stefan Dobrev
Computer Science
-
Chapter and Conference Paper
The Power of Tokens: Rendezvous and Symmetry Detection for Two Mobile Agents in a Ring
Rendezvous with detection differs from the usual rendezvous problem in that two mobile agents not only accomplish rendezvous whenever this is possible, but can also detect the impossibility of rendezvous (e.g....
-
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 ...
-
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
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
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
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
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...
-
Article
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...
-
Article
Advice Complexity of Maximum Independent set in Sparse and Bipartite Graphs
We study the advice complexity of the online version of the Maximum Independent Set problem, restricted to the sparse, and bipartite graphs, respectively. We show that for sparse graphs, constant-sized advice ...
-
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
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
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...
