Show simple item record

Synchronous Black Hole Search in Directed Graphs

hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorKOSOWSKI, Adrian
hal.structure.identifierDipartimento di Matematica e Informatica [Perugia] [DMI]
dc.contributor.authorNAVARRA, Alfredo
hal.structure.identifierDipartimento di Matematica e Informatica [Perugia] [DMI]
dc.contributor.authorPINOTTI, Cristina
dc.date.accessioned2024-04-15T09:47:06Z
dc.date.available2024-04-15T09:47:06Z
dc.date.issued2011-06-13
dc.identifier.issn1879-2294
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198066
dc.description.abstractEnThe paper considers a team of robots which has to explore a graph G where some nodes can be harmful. Robots are initially located at the so called home base node. The dangerous nodes are the so called black hole nodes, and once a robot enters in one of them, it is destroyed. The goal is to find a strategy in order to explore G in such a way that the minimum number of robots is wasted. The exploration ends if there is at least one surviving robot which knows all the edges leading to the black holes. As many variations of the problem have been considered so far, the solution and its measure heavily depend on the initial knowledge and the capabilities of the robots. In this paper, we assume that G is a directed graph, the robots are associated with unique identifiers, they know the number of nodes n of G (or at least an upper bound on n), and they know the number of edges Delta leading to the black holes. Each node is associated with a whiteboard where robots can read and write information in a mutual exclusive way. A recently posed question [Czyzowicz et al., Proc. SIROCCO'09] is whether some number of robots, expressed as a function of parameter Delta only, is suffi- cient to detect black holes in directed graphs of arbitrarily large order n. We give a positive answer to this question for the synchronous case, i.e., when the robots share a common clock, showing that O(Delta* 2^Delta) robots are sufficient to solve the problem. This bound is nearly tight, since it is known that at least 2^Delta robots are required for some instances. Quite surprisingly, we also show that unlike in the case of undirected graphs, for the directed version of the problem, synchronization can sometimes make a difference: for Delta = 2, in the synchronous case 4 robots are always sufficient, whereas in the asynchronous case at least 5 robots are sometimes required.
dc.language.isoen
dc.publisherElsevier
dc.title.enSynchronous Black Hole Search in Directed Graphs
dc.typeArticle de revue
dc.identifier.doi10.1016/j.tcs.2011.05.054
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
bordeaux.journalTheoretical Computer Science
bordeaux.page5752-5759
bordeaux.volume412
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.issue41
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierinria-00614476
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//inria-00614476v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Theoretical%20Computer%20Science&rft.date=2011-06-13&rft.volume=412&rft.issue=41&rft.spage=5752-5759&rft.epage=5752-5759&rft.eissn=1879-2294&rft.issn=1879-2294&rft.au=KOSOWSKI,%20Adrian&NAVARRA,%20Alfredo&PINOTTI,%20Cristina&rft.genre=article


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record