38 Result(s)
within
Stefan Dobrev
Chapter
Conference Paper
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
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,
-
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...
-
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...
-
Chapter and Conference Paper
Time and Message Optimal Leader Election in Asynchronous Oriented Complete Networks
We consider the problem of leader election in asynchronous oriented N-node complete networks. We present a leader election algorithm with O(N) message and O(log logN) time complexity. The message complexity is op...
-
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
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
Yet Another Modular Technique for Efficient Leader Election
In this paper we present a general and still flexible modular technique for the design of efficient leader election algorithms in N-node networks. Our approach can be viewed as a generalization of the previous me...
-
Chapter and Conference Paper
Broadcasting on Anonymous Unoriented Tori
We consider broadcasting on asynchronous anonymous totally unoriented n × m torus, where N=n·m is the number of nodes. We present a broadcasting algorithm with message complexity 1.43 N+O(n+m) and prove the lower...
