Afficher la notice abrégée

Approximation bounds for Black Hole Search problems

hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorKLASING, Ralf
hal.structure.identifierDepartment of Informatics and Telecomunications [Kapodistrian Univ] [DI NKUA]
dc.contributor.authorMARKOU, Euripides
hal.structure.identifierDepartment of Computer Science [DCS]
dc.contributor.authorRADZIK, Tomasz
hal.structure.identifierDipartimento di Informatica e Sistemistica "Antonio Ruberti" [DIS]
dc.contributor.authorSARRACCO, Fabiano
dc.date.accessioned2024-04-15T09:56:44Z
dc.date.available2024-04-15T09:56:44Z
dc.date.issued2007
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198861
dc.description.abstractEnA black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node without leaving any trace. The Black Hole Search is the task of locating all black holes in a network, through the exploration of its nodes by a set of mobile agents. In this paper we consider the problem of designing the fastest Black Hole Search, given the map of the network, the starting node and a subset of nodes of the network initially known to be safe. We study the version of this problem that assumes that there is at most one black hole in the network and there are two agents, which move in synchronized steps. We prove that this problem is not polynomial-time approximable within any constant factor less than 389/388 (unless PTIME=NPTIME). We give a 6-approximation algorithm, thus improving on the 9.3-approximation algorithm from [3]. We also prove APX-hardness for a restricted version of the problem, in which only the starting node is initially known to be safe.
dc.language.isoen
dc.title.enApproximation bounds for Black Hole Search problems
dc.typeRapport
dc.subject.halInformatique [cs]/Réseaux et télécommunications [cs.NI]
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.type.institutionINRIA
bordeaux.type.reportrr
hal.identifierinria-00145157
hal.version1
hal.audienceNon spécifiée
hal.origin.linkhttps://hal.archives-ouvertes.fr//inria-00145157v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2007&rft.au=KLASING,%20Ralf&MARKOU,%20Euripides&RADZIK,%20Tomasz&SARRACCO,%20Fabiano&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée