17 Result(s)
within
English
Computer Science
Algorithm Analysis and Problem Complexity
Data Structures
Stefan Dobrev
Conference Paper
-
Chapter and Conference Paper
Two Broadcasting Problems in FaultyHypercubes
We consider two broadcasting problems in the n-dimensional hypercube under the shouting communication mode, i.e. any node of a network can inform all its neighbours in one time step. In addition, during any ti...
-
Chapter and Conference Paper
Computing Input Multiplicity in Anonymous Synchronous Networks with Dynamic Faults
We consider the following problem: Each processor of the network has assigned a (not necessarily unique) input value. Determine multiplicity of each input value. Solving this problem means any input-symmetric ...
-
Chapter and Conference Paper
Improved Bounds for Optimal Black Hole Search with a Network Map
A black hole is a harmful host that destroys incoming agents without leaving any observable trace of such a destruction. The black hole search problem is to unambiguously determine the location of the black hole....
-
Chapter and Conference Paper
Finding Short Right-Hand-on-the-Wall Walks in Graphs
We consider the problem of perpetual traversal by a single agent in an anonymous undirected graph G. Our requirements are: (1) deterministic algorithm, (2) each node is visited within O(n) moves, (3) the agent us...
-
Chapter and Conference Paper
Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges
We give an algorithm for constructing a connected spanning subgraphs(panner) of a wireless network modelled as a unit disk graph with nodes of irregular transmission ranges, whereby for some parameter 0 < r ≤ 1 t...
-
Chapter and Conference Paper
On Fractional Dynamic Faults with Threshold
Unlike localized communication failures that occur on a fixed (although a priori unknown) set of links, dynamic faults can occur on any link. Known also as mobile or ubiquitous faults, their presence makes many t...
-
Chapter and Conference Paper
Local Edge Colouring of Yao-Like Subgraphs of Unit Disk Graphs
The focus of the present paper is on providing a local deterministic algorithm for colouring the edges of Yao-like subgraphs of Unit Disc Graphs. These are geometric graphs such that for some positive integers l,
-
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
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
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
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
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...
