45 Result(s)
within
Stefan Dobrev
Computer Science
English
-
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...
-
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 ...
-
Article
Mobile Search for a Black Hole in an Anonymous Ring
In this paper we address the problem of mobile agents searching for a highly harmful item (called a black hole) in a ring network. The black hole is a stationary process that destroys visiting agents upon thei...
-
Chapter and Conference Paper
Locating a Black Hole in an Un-oriented Ring Using Tokens: The Case of Scattered Agents
Black hole search in a ring network has been studied in a token model. It is known that locating the black hole in an anonymous ring using tokens is feasible, if the team of agents is initially co-located. When d...
-
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,
-
Article
Searching for a black hole in arbitrary networks: optimal mobile agents protocols
Consider a networked environment, supporting mobile agents, where there is a black hole: a harmful host that disposes of visiting agents upon their arrival, leaving no observable trace of such a destruction. T...
-
Chapter and Conference Paper
Half-Space Proximal: A New Local Test for Extracting a Bounded Dilation Spanner of a Unit Disk Graph
We give a new local test, called a Half-Space Proximal or HSP test, for extracting a sparse directed or undirected subgraph of a given unit disk graph. The HSP neighbors of each vertex are unique, given a fixed u...
-
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
Exploring an Unknown Graph to Locate a Black Hole Using Tokens
Consider a team of (one or more) mobile agents operating in a graph G. Unaware of the graph topology and starting from the same node, the team must explore the graph. This problem, known as graph exploration, was...
-
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
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
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
Multiple Agents RendezVous in a Ring in Spite of a Black Hole
The Rendezvous of anonymous mobile agents in a anonymous network is an intensively studied problem; it calls for k anonymous, mobile agents to gather in the same site. We study this problem when in the network th...
-
Article
Communication-Efficient Broadcasting in Complete Networks with Dynamic Faults
We consider the problem of message (and bit) efficient broadcasting in complete networks with dynamic faults. Despite the simplicity of the setting, the problem turned out to be surprisingly interesting from ...
-
Chapter and Conference Paper
Mobile Search for a Black Hole in an Anonymous Ring
We address the problem of mobile agents searching a ring network for a highly harmful item, a black hole, a stationary process destroying visiting agents upon their arrival.No observable trace of such a destructi...
-
Chapter and Conference Paper
Optimal Broadcasting in Even Tori with Dynamic Faults
We consider a broadcasting problem in the n-dimensional k-ary even torus in the shouting communication mode, i.e. any node of a network can inform all its neighbours in one time step. In addition, during any time...
