|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 3 van 11 gevonden artikelen
| Titel: |
Complexity of Searching for a Black Hole |
| Auteur: |
Czyzowicz, Jurek Kowalski, Dariusz Markou, Euripides Pelc, Andrzej |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 71 (2006) nr. 2-3 pagina's 229-242 |
| Jaar: |
2006-06-15 |
| Inhoud: |
A 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. We consider the task of locating a black hole in a (partially) synchronous network, assuming an upper bound on the time of any edge traversal by an agent. The minimum number of agents capable to identify a black hole is two. For a given graph and given starting node we are interested in the fastest possible black hole search by two agents, under the general scenario in which some subset of nodes is safe and the black hole can be located in one of the remaining nodes. We show that the problem of finding the fastest possible black hole search scheme by two agents is NP-hard, and we give a 9.3-approximation for it. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 3 van 11 gevonden artikelen
| << vorige | volgende >> |