21 Result(s)
within
English
Computer Science
Theory of Computation
Stefan Dobrev
-
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
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
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...
-
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...
-
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...
-
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....
-
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 ...
-
Article
Weak Coverage of a Rectangular Barrier
Assume n wireless mobile sensors are initially dispersed in an ad hoc manner in a rectangular region. Each sensor can monitor a circular area of specific diameter around its position, called the sensor diameter. ...
-
Chapter and Conference Paper
Graph Exploration by Energy-Sharing Mobile Agents
We consider the problem of collective exploration of a known n-node edge-weighted graph by k mobile agents that have limited energy but are capable of energy transfers. The agents are initially placed at an arbit...
