Mobile Search for a Black Hole in an Anonymous Ring View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2007-05

AUTHORS

Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro

ABSTRACT

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 their arrival without leaving any observable trace of such a destruction. The task is to have at least one surviving agent able to unambiguously report the location of the black hole. We consider different scenarios and in each situation we answer some computational as well as complexity questions. We first consider agents that start from the same home base (co-located). We prove that two such agents are necessary and sufficient to locate the black hole; in our algorithm the agents perform O(n log n) moves (where n is the size of the ring) and we show that such a bound is optimal. We also consider time complexity and show how to achieve the optimal bound of 2n - 4 units of time using n - 1 agents. We generalize our technique to establish a trade-off between time and number of agents. We then consider the case of agents that start from different home bases (dispersed) and we show that if the ring is oriented, two dispersed agents are still necessary and sufficient. Also in this case our algorithm is optimal in terms of number of moves (Θ(n log n)). We finally show that if the ring is unoriented, three agents are necessary and sufficient; an optimal algorithm follows from the oriented case. More... »

PAGES

67-90

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-006-1232-z

DOI

http://dx.doi.org/10.1007/s00453-006-1232-z

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1027520360


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Ottawa", 
          "id": "https://www.grid.ac/institutes/grid.28046.38", 
          "name": [
            "School of Information Technology and Engineering, University of Ottawa, Ottawa, Ontario, K1N 6N5, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dobrev", 
        "givenName": "Stefan", 
        "id": "sg:person.0610371471.49", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0610371471.49"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Ottawa", 
          "id": "https://www.grid.ac/institutes/grid.28046.38", 
          "name": [
            "School of Information Technology and Engineering, University of Ottawa, Ottawa, Ontario, K1N 6N5, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Flocchini", 
        "givenName": "Paola", 
        "id": "sg:person.011601470625.25", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011601470625.25"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Pisa", 
          "id": "https://www.grid.ac/institutes/grid.5395.a", 
          "name": [
            "Dipartimento di Informatica, Universita di Pisa, Pisa, 56100, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Prencipe", 
        "givenName": "Giuseppe", 
        "id": "sg:person.011355366403.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011355366403.28"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Carleton University", 
          "id": "https://www.grid.ac/institutes/grid.34428.39", 
          "name": [
            "Department of Computer Science, Carleton University, Ottawa, Ontario, K1S 5B6, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Santoro", 
        "givenName": "Nicola", 
        "id": "sg:person.010566557723.84", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010566557723.84"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2007-05", 
    "datePublishedReg": "2007-05-01", 
    "description": "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 their arrival without leaving any observable trace of such a destruction. The task is to have at least one surviving agent able to unambiguously report the location of the black hole. We consider different scenarios and in each situation we answer some computational as well as complexity questions. We first consider agents that start from the same home base (co-located). We prove that two such agents are necessary and sufficient to locate the black hole; in our algorithm the agents perform O(n log n) moves (where n is the size of the ring) and we show that such a bound is optimal. We also consider time complexity and show how to achieve the optimal bound of 2n - 4 units of time using n - 1 agents. We generalize our technique to establish a trade-off between time and number of agents. We then consider the case of agents that start from different home bases (dispersed) and we show that if the ring is oriented, two dispersed agents are still necessary and sufficient. Also in this case our algorithm is optimal in terms of number of moves (\u0398(n log n)). We finally show that if the ring is unoriented, three agents are necessary and sufficient; an optimal algorithm follows from the oriented case.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00453-006-1232-z", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "48"
      }
    ], 
    "name": "Mobile Search for a Black Hole in an Anonymous Ring", 
    "pagination": "67-90", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "83197d743a9fbab8d429fc76cbe1b9402dbd4814f97fc32ef562954783e40e44"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-006-1232-z"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1027520360"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-006-1232-z", 
      "https://app.dimensions.ai/details/publication/pub.1027520360"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T18:20", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8675_00000513.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2Fs00453-006-1232-z"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00453-006-1232-z'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00453-006-1232-z'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-006-1232-z'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-006-1232-z'


 

This table displays all metadata directly associated to this object as RDF triples.

88 TRIPLES      20 PREDICATES      27 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-006-1232-z schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N68130a21cff7479cba66676d63e8a026
4 schema:datePublished 2007-05
5 schema:datePublishedReg 2007-05-01
6 schema:description 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 their arrival without leaving any observable trace of such a destruction. The task is to have at least one surviving agent able to unambiguously report the location of the black hole. We consider different scenarios and in each situation we answer some computational as well as complexity questions. We first consider agents that start from the same home base (co-located). We prove that two such agents are necessary and sufficient to locate the black hole; in our algorithm the agents perform O(n log n) moves (where n is the size of the ring) and we show that such a bound is optimal. We also consider time complexity and show how to achieve the optimal bound of 2n - 4 units of time using n - 1 agents. We generalize our technique to establish a trade-off between time and number of agents. We then consider the case of agents that start from different home bases (dispersed) and we show that if the ring is oriented, two dispersed agents are still necessary and sufficient. Also in this case our algorithm is optimal in terms of number of moves (Θ(n log n)). We finally show that if the ring is unoriented, three agents are necessary and sufficient; an optimal algorithm follows from the oriented case.
7 schema:genre research_article
8 schema:inLanguage en
9 schema:isAccessibleForFree true
10 schema:isPartOf N37e32c3fb1164113b4ed7ed29dea1298
11 N5a6607c0bbfa42fe9308b964162bef32
12 sg:journal.1047644
13 schema:name Mobile Search for a Black Hole in an Anonymous Ring
14 schema:pagination 67-90
15 schema:productId N0bc63811a839426386a3208905430383
16 N3218c451fa364bacb4c8f1ce28b5de92
17 Nf86789fa2421480eaa617c4af88d991e
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027520360
19 https://doi.org/10.1007/s00453-006-1232-z
20 schema:sdDatePublished 2019-04-10T18:20
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher N58748383b3a541d3a1b9ec0554ccec2c
23 schema:url http://link.springer.com/10.1007%2Fs00453-006-1232-z
24 sgo:license sg:explorer/license/
25 sgo:sdDataset articles
26 rdf:type schema:ScholarlyArticle
27 N0098f2dfa4f0481ab36cda9c448c7ab7 rdf:first sg:person.011355366403.28
28 rdf:rest Nf08c2a3ff3294ff6ab346c22982fa492
29 N0bc63811a839426386a3208905430383 schema:name doi
30 schema:value 10.1007/s00453-006-1232-z
31 rdf:type schema:PropertyValue
32 N10db91a332cd425da7327f7b09d0eec8 rdf:first sg:person.011601470625.25
33 rdf:rest N0098f2dfa4f0481ab36cda9c448c7ab7
34 N3218c451fa364bacb4c8f1ce28b5de92 schema:name dimensions_id
35 schema:value pub.1027520360
36 rdf:type schema:PropertyValue
37 N37e32c3fb1164113b4ed7ed29dea1298 schema:issueNumber 1
38 rdf:type schema:PublicationIssue
39 N58748383b3a541d3a1b9ec0554ccec2c schema:name Springer Nature - SN SciGraph project
40 rdf:type schema:Organization
41 N5a6607c0bbfa42fe9308b964162bef32 schema:volumeNumber 48
42 rdf:type schema:PublicationVolume
43 N68130a21cff7479cba66676d63e8a026 rdf:first sg:person.0610371471.49
44 rdf:rest N10db91a332cd425da7327f7b09d0eec8
45 Nf08c2a3ff3294ff6ab346c22982fa492 rdf:first sg:person.010566557723.84
46 rdf:rest rdf:nil
47 Nf86789fa2421480eaa617c4af88d991e schema:name readcube_id
48 schema:value 83197d743a9fbab8d429fc76cbe1b9402dbd4814f97fc32ef562954783e40e44
49 rdf:type schema:PropertyValue
50 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
51 schema:name Information and Computing Sciences
52 rdf:type schema:DefinedTerm
53 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
54 schema:name Artificial Intelligence and Image Processing
55 rdf:type schema:DefinedTerm
56 sg:journal.1047644 schema:issn 0178-4617
57 1432-0541
58 schema:name Algorithmica
59 rdf:type schema:Periodical
60 sg:person.010566557723.84 schema:affiliation https://www.grid.ac/institutes/grid.34428.39
61 schema:familyName Santoro
62 schema:givenName Nicola
63 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010566557723.84
64 rdf:type schema:Person
65 sg:person.011355366403.28 schema:affiliation https://www.grid.ac/institutes/grid.5395.a
66 schema:familyName Prencipe
67 schema:givenName Giuseppe
68 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011355366403.28
69 rdf:type schema:Person
70 sg:person.011601470625.25 schema:affiliation https://www.grid.ac/institutes/grid.28046.38
71 schema:familyName Flocchini
72 schema:givenName Paola
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011601470625.25
74 rdf:type schema:Person
75 sg:person.0610371471.49 schema:affiliation https://www.grid.ac/institutes/grid.28046.38
76 schema:familyName Dobrev
77 schema:givenName Stefan
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0610371471.49
79 rdf:type schema:Person
80 https://www.grid.ac/institutes/grid.28046.38 schema:alternateName University of Ottawa
81 schema:name School of Information Technology and Engineering, University of Ottawa, Ottawa, Ontario, K1N 6N5, Canada
82 rdf:type schema:Organization
83 https://www.grid.ac/institutes/grid.34428.39 schema:alternateName Carleton University
84 schema:name Department of Computer Science, Carleton University, Ottawa, Ontario, K1S 5B6, Canada
85 rdf:type schema:Organization
86 https://www.grid.ac/institutes/grid.5395.a schema:alternateName University of Pisa
87 schema:name Dipartimento di Informatica, Universita di Pisa, Pisa, 56100, Italy
88 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...