Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(5)
Asymptotic Optimality
Ring Network
Time Complexity
Timing Optimization
Black Hole
Subscribe
Academic
Publications
Time Optimal Algorithms for Black Hole Search in Rings
Time Optimal Algorithms for Black Hole Search in Rings,10.1007/9783642174612_5,Balasingham Balamohan,Paola Flocchini,Ali Miri,Nicola Santoro
Edit
Time Optimal Algorithms for Black Hole Search in Rings
(
Citations: 2
)
BibTex

RIS

RefWorks
Download
Balasingham Balamohan
,
Paola Flocchini
,
Ali Miri
,
Nicola Santoro
In a network environments supporting mobile entities (called robots or agents), a
black hole
is harmful site that destroys any incoming entity without leaving any visible trace. The blackhole search problem is the task of a team of k > 1 mobile entities, starting from the same safe location and executing the same algorithm, to determine within finite time the location of the black hole. In this paper we consider the
black hole
search problem in asynchronous ring networks of n nodes, and focus on the time complexity. It is known that any algorithm for blackhole search in a ring requires at least 2(n − 2) time in the worst case. The best algorithm achieves this bound with a team of n − 1 agents with an average time cost 2(n − 2), equal to the worst case. In this paper we first show how the same number of agents using 2 extra time units from optimal in the worst case, can solve the problem in only \frac74 n</font >O(1)\frac{7}{4} nO(1) time on the average. We then prove that the optimal average case complexity \frac32 n</font >O(1)\frac{3}{2} nO(1) can be achieved without increasing the worst case using 2(n − 1) agents Finally we design an algorithm that achieves asymptotically optimal both worst case and average case
time complexity
employing an optimal team of k = 2 agents, thus improving on the earlier results that required O(n) agents.
Conference:
Conference on Combinatorial Optimization and Applications  COCOA
, pp. 5871, 2010
DOI:
10.1007/9783642174612_5
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
adsabs.harvard.edu
)
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
More »
Citation Context
(2)
...Recently, the optimality of black hole search has been studied in [
2
]...
Paola Flocchini
,
et al.
Searching for Black Holes in Subways
...The number of agents has been recently reduced to 2, but the number of moves is still quadratic [
1
]...
...Our solution improves the existing results of [12,
1
] which use a quadratic number of moves...
...Recently, we have shown that an asymptotically optimal Θ(n) bound can be achieved using only 2 agents [
1
]; the number of moves is however still O(n 2 ). We now describe the first protocol that is optimal simultaneously in all three complexity measures: asymptotically in time ,a nd exactly in cost and size...
Balasingham Balamohan
,
et al.
Improving the Optimal Bounds for Black Hole Search in Rings
References
(27)
The power of a pebble: exploring and mapping directed graphs
(
Citations: 101
)
Michael A. Bender
,
Antonio Fernfindezt
,
Dana Ron
,
Amit Sahai
,
Salil P. Vadhan
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 269278, 1998
Searching for BlackHole Faults in a Network Using Multiple Agents
(
Citations: 22
)
Colin Cooper
,
Ralf Klasing
,
Tomasz Radzik
Conference:
International Conference On Principles Of DIstributed Systems  OPODIS
, pp. 320332, 2006
Complexity of Searching for a Black Hole
(
Citations: 17
)
Jurek Czyzowicz
,
Dariusz R. Kowalski
,
Euripides Markou
,
Andrzej Pelc
Journal:
Fundamenta Informaticae  FUIN
, vol. 71, no. 23, pp. 229242, 2006
Searching for a Black Hole in Synchronous Tree Networks
(
Citations: 13
)
Jurek Czyzowicz
,
Dariusz R. Kowalski
,
Euripides Markou
,
Andrzej Pelc
Journal:
Combinatorics, Probability & Computing  CPC
, vol. 16, no. 4, pp. 595619, 2007
Exploring an unknown graph
(
Citations: 134
)
Xiaotie Deng
,
C.H. Papadimitriou
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, 1990
Sort by:
Citations
(2)
Searching for Black Holes in Subways
(
Citations: 1
)
Paola Flocchini
,
Matthew Kellett
,
Peter C. Mason
,
Nicola Santoro
Journal:
Theory of Computing Systems / Mathematical Systems Theory  MST
, pp. 127
Improving the Optimal Bounds for Black Hole Search in Rings
Balasingham Balamohan
,
Paola Flocchini
,
Ali Miri
,
Nicola Santoro