45 Result(s)
within
Stefan Dobrev
Computer Science
English
-
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...
-
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
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
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...
-
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
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
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
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...
-
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
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
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
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...
