Searching for a black hole in arbitrary networks: optimal mobile agents protocols View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2006-09

AUTHORS

Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro

ABSTRACT

Consider a networked environment, supporting mobile agents, where there is a black hole: a harmful host that disposes of visiting agents upon their arrival, leaving no observable trace of such a destruction. The black hole search problem is the one of assembling a team of asynchronous mobile agents, executing the same protocol and communicating by means of whiteboards, to successfully identify the location of the black hole; we are concerned with solutions that are generic (i.e., topology-independent). We establish tight bounds on the size of the team (i.e., the number of agents), and the cost (i.e., the number of moves) of a size-optimal solution protocol. These bounds depend on the a priori knowledge the agents have about the network, and on the consistency of the local labelings. In particular, we prove that: with topological ignorance Δ+1 agents are needed and suffice, and the cost is Θ(n2), where Δ is the maximal degree of a node and n is the number of nodes in the network; with topological ignorance but in presence of sense of direction only two agents suffice and the cost is Θ(n2); and with complete topological knowledge only two agents suffice and the cost is Θ(n log n). All the upper-bound proofs are constructive. More... »

PAGES

1-99999

References to SciGraph publications

  • 2003. Deterministic Rendezvous in Graphs in ALGORITHMS - ESA 2003
  • 1998. Protecting Mobile Agents Against Malicious Hosts in MOBILE AGENTS AND SECURITY
  • 1998. Time Limited Blackbox Security: Protecting Mobile Agents From Malicious Hosts in MOBILE AGENTS AND SECURITY
  • 1996. Agent rendezvous: A dynamic symmetry-breaking problem in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2007-02. Rendezvous and Election of Mobile Agents: Impact of Sense of Direction in THEORY OF COMPUTING SYSTEMS
  • 1977-09. A homology theory for spanning tress of a graph in ACTA MATHEMATICA
  • 1999-04-15. Mobile Agent Security — Issues and Directions in INTELLIGENCE IN SERVICES AND NETWORKS PAVING THE WAY FOR AN OPEN SERVICE MARKET
  • 2004. Collective Tree Exploration in LATIN 2004: THEORETICAL INFORMATICS
  • 1998. Security Issues in Mobile Code Systems in MOBILE AGENTS AND SECURITY
  • 2003. Host Revocation Authority: A Way of Protecting Mobile Agents from Malicious Hosts in WEB ENGINEERING
  • 2002. Optimal Graph Exploration without Good Maps in ALGORITHMS — ESA 2002
  • 2004. Graph Exploration by a Finite Automaton in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2004
  • 1980-03. Automaten in planaren Graphen in ACTA INFORMATICA
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00446-006-0154-y

    DOI

    http://dx.doi.org/10.1007/s00446-006-0154-y

    DIMENSIONS

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


    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/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical 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, 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, 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, Universit\u00e0 di Pisa, 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": [
                "School of Computer Science, Carleton University, Ottawa, Ontario, 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"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-540-24698-5_18", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004608467", 
              "https://doi.org/10.1007/978-3-540-24698-5_18"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-24698-5_18", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004608467", 
              "https://doi.org/10.1007/978-3-540-24698-5_18"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0004-3702(99)00107-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007552506"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/(sici)1097-0037(199810)32:3<165::aid-net1>3.0.co;2-i", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009826280"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/(sici)1097-0118(199911)32:3<265::aid-jgt6>3.0.co;2-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010742782"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/274787.274788", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010783463"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00288647", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013616124", 
              "https://doi.org/10.1007/bf00288647"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jagm.1999.1043", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014281330"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-39658-1_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014373401", 
              "https://doi.org/10.1007/978-3-540-39658-1_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-39658-1_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014373401", 
              "https://doi.org/10.1007/978-3-540-39658-1_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/inco.1999.2795", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015653445"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/276698.276759", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022410991"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-28629-5_34", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022544006", 
              "https://doi.org/10.1007/978-3-540-28629-5_34"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-28629-5_34", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022544006", 
              "https://doi.org/10.1007/978-3-540-28629-5_34"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-68671-1_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024187435", 
              "https://doi.org/10.1007/3-540-68671-1_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-68671-1_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025297124", 
              "https://doi.org/10.1007/3-540-68671-1_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0140-3664(99)00083-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028258284"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-005-1223-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029611870", 
              "https://doi.org/10.1007/s00224-005-1223-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45749-6_35", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031202004", 
              "https://doi.org/10.1007/3-540-45749-6_35"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45068-8_54", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037532085", 
              "https://doi.org/10.1007/3-540-45068-8_54"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-61440-0_163", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038487864", 
              "https://doi.org/10.1007/3-540-61440-0_163"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48888-x_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042407702", 
              "https://doi.org/10.1007/3-540-48888-x_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48888-x_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042407702", 
              "https://doi.org/10.1007/3-540-48888-x_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/777412.777469", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043112318"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0166-218x(95)00054-u", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043686576"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jalgor.2003.10.002", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045412441"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-68671-1_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046618128", 
              "https://doi.org/10.1007/3-540-68671-1_1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0304-3975(01)00395-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048652636"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01896190", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050830116", 
              "https://doi.org/10.1007/bf01896190"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/564870.564906", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051619886"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/35.689634", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061159636"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/70.105395", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061215884"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0207017", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841411"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0097539700377293", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062879258"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0097539791194931", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062879656"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s009753979732428x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062880193"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1239/jap/1032374243", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064441573"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1978.30", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086207665"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1994.365703", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093260501"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/icdcs.2003.1203510", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093976351"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/icdcs.2000.840953", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094334627"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/isads.1999.838454", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095053032"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2006-09", 
        "datePublishedReg": "2006-09-01", 
        "description": "Consider a networked environment, supporting mobile agents, where there is a black hole: a harmful host that disposes of visiting agents upon their arrival, leaving no observable trace of such a destruction. The black hole search problem is the one of assembling a team of asynchronous mobile agents, executing the same protocol and communicating by means of whiteboards, to successfully identify the location of the black hole; we are concerned with solutions that are generic (i.e., topology-independent). We establish tight bounds on the size of the team (i.e., the number of agents), and the cost (i.e., the number of moves) of a size-optimal solution protocol. These bounds depend on the a priori knowledge the agents have about the network, and on the consistency of the local labelings. In particular, we prove that: with topological ignorance \u0394+1 agents are needed and suffice, and the cost is \u0398(n2), where \u0394 is the maximal degree of a node and n is the number of nodes in the network; with topological ignorance but in presence of sense of direction only two agents suffice and the cost is \u0398(n2); and with complete topological knowledge only two agents suffice and the cost is \u0398(n log n). All the upper-bound proofs are constructive.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00446-006-0154-y", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1052621", 
            "issn": [
              "0178-2770", 
              "1432-0452"
            ], 
            "name": "Distributed Computing", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "19"
          }
        ], 
        "name": "Searching for a black hole in arbitrary networks: optimal mobile agents protocols", 
        "pagination": "1-99999", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "045de802154b97dec63be03dad2f1fb2d2fb631e8b07108b5d69cfaa2098d20c"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00446-006-0154-y"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1000916693"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00446-006-0154-y", 
          "https://app.dimensions.ai/details/publication/pub.1000916693"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T12:54", 
        "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/0000000364_0000000364/records_72867_00000000.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/s00446-006-0154-y"
      }
    ]
     

    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/s00446-006-0154-y'

    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/s00446-006-0154-y'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00446-006-0154-y'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00446-006-0154-y'


     

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

    215 TRIPLES      21 PREDICATES      65 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00446-006-0154-y schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N8308f1116fcf4ba9ae8c3f47c910ec8f
    4 schema:citation sg:pub.10.1007/3-540-45068-8_54
    5 sg:pub.10.1007/3-540-45749-6_35
    6 sg:pub.10.1007/3-540-48888-x_16
    7 sg:pub.10.1007/3-540-61440-0_163
    8 sg:pub.10.1007/3-540-68671-1_1
    9 sg:pub.10.1007/3-540-68671-1_4
    10 sg:pub.10.1007/3-540-68671-1_6
    11 sg:pub.10.1007/978-3-540-24698-5_18
    12 sg:pub.10.1007/978-3-540-28629-5_34
    13 sg:pub.10.1007/978-3-540-39658-1_19
    14 sg:pub.10.1007/bf00288647
    15 sg:pub.10.1007/bf01896190
    16 sg:pub.10.1007/s00224-005-1223-5
    17 https://doi.org/10.1002/(sici)1097-0037(199810)32:3<165::aid-net1>3.0.co;2-i
    18 https://doi.org/10.1002/(sici)1097-0118(199911)32:3<265::aid-jgt6>3.0.co;2-8
    19 https://doi.org/10.1006/inco.1999.2795
    20 https://doi.org/10.1006/jagm.1999.1043
    21 https://doi.org/10.1016/0166-218x(95)00054-u
    22 https://doi.org/10.1016/j.jalgor.2003.10.002
    23 https://doi.org/10.1016/s0004-3702(99)00107-1
    24 https://doi.org/10.1016/s0140-3664(99)00083-3
    25 https://doi.org/10.1016/s0304-3975(01)00395-4
    26 https://doi.org/10.1109/35.689634
    27 https://doi.org/10.1109/70.105395
    28 https://doi.org/10.1109/icdcs.2000.840953
    29 https://doi.org/10.1109/icdcs.2003.1203510
    30 https://doi.org/10.1109/isads.1999.838454
    31 https://doi.org/10.1109/sfcs.1978.30
    32 https://doi.org/10.1109/sfcs.1994.365703
    33 https://doi.org/10.1137/0207017
    34 https://doi.org/10.1137/s0097539700377293
    35 https://doi.org/10.1137/s0097539791194931
    36 https://doi.org/10.1137/s009753979732428x
    37 https://doi.org/10.1145/274787.274788
    38 https://doi.org/10.1145/276698.276759
    39 https://doi.org/10.1145/564870.564906
    40 https://doi.org/10.1145/777412.777469
    41 https://doi.org/10.1239/jap/1032374243
    42 schema:datePublished 2006-09
    43 schema:datePublishedReg 2006-09-01
    44 schema:description Consider a networked environment, supporting mobile agents, where there is a black hole: a harmful host that disposes of visiting agents upon their arrival, leaving no observable trace of such a destruction. The black hole search problem is the one of assembling a team of asynchronous mobile agents, executing the same protocol and communicating by means of whiteboards, to successfully identify the location of the black hole; we are concerned with solutions that are generic (i.e., topology-independent). We establish tight bounds on the size of the team (i.e., the number of agents), and the cost (i.e., the number of moves) of a size-optimal solution protocol. These bounds depend on the a priori knowledge the agents have about the network, and on the consistency of the local labelings. In particular, we prove that: with topological ignorance Δ+1 agents are needed and suffice, and the cost is Θ(n2), where Δ is the maximal degree of a node and n is the number of nodes in the network; with topological ignorance but in presence of sense of direction only two agents suffice and the cost is Θ(n2); and with complete topological knowledge only two agents suffice and the cost is Θ(n log n). All the upper-bound proofs are constructive.
    45 schema:genre research_article
    46 schema:inLanguage en
    47 schema:isAccessibleForFree true
    48 schema:isPartOf N131004a7444143b1a1dd72fc1d412303
    49 Nf19f034b9cc04a25981072c8111d8a42
    50 sg:journal.1052621
    51 schema:name Searching for a black hole in arbitrary networks: optimal mobile agents protocols
    52 schema:pagination 1-99999
    53 schema:productId N6d1c30375b0146289701fd9829703863
    54 Nb2aa7089bc604cc48cd1ef16ca68d7a1
    55 Nba3e19a9925f4f58b1c88a1107b7f096
    56 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000916693
    57 https://doi.org/10.1007/s00446-006-0154-y
    58 schema:sdDatePublished 2019-04-11T12:54
    59 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    60 schema:sdPublisher Nf9c8ad3dc6cd4f40b0459acd7a517fe2
    61 schema:url http://link.springer.com/10.1007/s00446-006-0154-y
    62 sgo:license sg:explorer/license/
    63 sgo:sdDataset articles
    64 rdf:type schema:ScholarlyArticle
    65 N131004a7444143b1a1dd72fc1d412303 schema:volumeNumber 19
    66 rdf:type schema:PublicationVolume
    67 N184dd034268f4a75a37af203024a8f6d rdf:first sg:person.010566557723.84
    68 rdf:rest rdf:nil
    69 N6d1c30375b0146289701fd9829703863 schema:name doi
    70 schema:value 10.1007/s00446-006-0154-y
    71 rdf:type schema:PropertyValue
    72 N8308f1116fcf4ba9ae8c3f47c910ec8f rdf:first sg:person.0610371471.49
    73 rdf:rest Nc7c424acde064c1695f665a189fe8ab7
    74 Nb2aa7089bc604cc48cd1ef16ca68d7a1 schema:name dimensions_id
    75 schema:value pub.1000916693
    76 rdf:type schema:PropertyValue
    77 Nba3e19a9925f4f58b1c88a1107b7f096 schema:name readcube_id
    78 schema:value 045de802154b97dec63be03dad2f1fb2d2fb631e8b07108b5d69cfaa2098d20c
    79 rdf:type schema:PropertyValue
    80 Nc7c424acde064c1695f665a189fe8ab7 rdf:first sg:person.011601470625.25
    81 rdf:rest Nfef492166b7e497eb6e7b2ce7221de35
    82 Nf19f034b9cc04a25981072c8111d8a42 schema:issueNumber 1
    83 rdf:type schema:PublicationIssue
    84 Nf9c8ad3dc6cd4f40b0459acd7a517fe2 schema:name Springer Nature - SN SciGraph project
    85 rdf:type schema:Organization
    86 Nfef492166b7e497eb6e7b2ce7221de35 rdf:first sg:person.011355366403.28
    87 rdf:rest N184dd034268f4a75a37af203024a8f6d
    88 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    89 schema:name Mathematical Sciences
    90 rdf:type schema:DefinedTerm
    91 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    92 schema:name Pure Mathematics
    93 rdf:type schema:DefinedTerm
    94 sg:journal.1052621 schema:issn 0178-2770
    95 1432-0452
    96 schema:name Distributed Computing
    97 rdf:type schema:Periodical
    98 sg:person.010566557723.84 schema:affiliation https://www.grid.ac/institutes/grid.34428.39
    99 schema:familyName Santoro
    100 schema:givenName Nicola
    101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010566557723.84
    102 rdf:type schema:Person
    103 sg:person.011355366403.28 schema:affiliation https://www.grid.ac/institutes/grid.5395.a
    104 schema:familyName Prencipe
    105 schema:givenName Giuseppe
    106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011355366403.28
    107 rdf:type schema:Person
    108 sg:person.011601470625.25 schema:affiliation https://www.grid.ac/institutes/grid.28046.38
    109 schema:familyName Flocchini
    110 schema:givenName Paola
    111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011601470625.25
    112 rdf:type schema:Person
    113 sg:person.0610371471.49 schema:affiliation https://www.grid.ac/institutes/grid.28046.38
    114 schema:familyName Dobrev
    115 schema:givenName Stefan
    116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0610371471.49
    117 rdf:type schema:Person
    118 sg:pub.10.1007/3-540-45068-8_54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037532085
    119 https://doi.org/10.1007/3-540-45068-8_54
    120 rdf:type schema:CreativeWork
    121 sg:pub.10.1007/3-540-45749-6_35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031202004
    122 https://doi.org/10.1007/3-540-45749-6_35
    123 rdf:type schema:CreativeWork
    124 sg:pub.10.1007/3-540-48888-x_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042407702
    125 https://doi.org/10.1007/3-540-48888-x_16
    126 rdf:type schema:CreativeWork
    127 sg:pub.10.1007/3-540-61440-0_163 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038487864
    128 https://doi.org/10.1007/3-540-61440-0_163
    129 rdf:type schema:CreativeWork
    130 sg:pub.10.1007/3-540-68671-1_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046618128
    131 https://doi.org/10.1007/3-540-68671-1_1
    132 rdf:type schema:CreativeWork
    133 sg:pub.10.1007/3-540-68671-1_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024187435
    134 https://doi.org/10.1007/3-540-68671-1_4
    135 rdf:type schema:CreativeWork
    136 sg:pub.10.1007/3-540-68671-1_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025297124
    137 https://doi.org/10.1007/3-540-68671-1_6
    138 rdf:type schema:CreativeWork
    139 sg:pub.10.1007/978-3-540-24698-5_18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004608467
    140 https://doi.org/10.1007/978-3-540-24698-5_18
    141 rdf:type schema:CreativeWork
    142 sg:pub.10.1007/978-3-540-28629-5_34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022544006
    143 https://doi.org/10.1007/978-3-540-28629-5_34
    144 rdf:type schema:CreativeWork
    145 sg:pub.10.1007/978-3-540-39658-1_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014373401
    146 https://doi.org/10.1007/978-3-540-39658-1_19
    147 rdf:type schema:CreativeWork
    148 sg:pub.10.1007/bf00288647 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013616124
    149 https://doi.org/10.1007/bf00288647
    150 rdf:type schema:CreativeWork
    151 sg:pub.10.1007/bf01896190 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050830116
    152 https://doi.org/10.1007/bf01896190
    153 rdf:type schema:CreativeWork
    154 sg:pub.10.1007/s00224-005-1223-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029611870
    155 https://doi.org/10.1007/s00224-005-1223-5
    156 rdf:type schema:CreativeWork
    157 https://doi.org/10.1002/(sici)1097-0037(199810)32:3<165::aid-net1>3.0.co;2-i schema:sameAs https://app.dimensions.ai/details/publication/pub.1009826280
    158 rdf:type schema:CreativeWork
    159 https://doi.org/10.1002/(sici)1097-0118(199911)32:3<265::aid-jgt6>3.0.co;2-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010742782
    160 rdf:type schema:CreativeWork
    161 https://doi.org/10.1006/inco.1999.2795 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015653445
    162 rdf:type schema:CreativeWork
    163 https://doi.org/10.1006/jagm.1999.1043 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014281330
    164 rdf:type schema:CreativeWork
    165 https://doi.org/10.1016/0166-218x(95)00054-u schema:sameAs https://app.dimensions.ai/details/publication/pub.1043686576
    166 rdf:type schema:CreativeWork
    167 https://doi.org/10.1016/j.jalgor.2003.10.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045412441
    168 rdf:type schema:CreativeWork
    169 https://doi.org/10.1016/s0004-3702(99)00107-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007552506
    170 rdf:type schema:CreativeWork
    171 https://doi.org/10.1016/s0140-3664(99)00083-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028258284
    172 rdf:type schema:CreativeWork
    173 https://doi.org/10.1016/s0304-3975(01)00395-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048652636
    174 rdf:type schema:CreativeWork
    175 https://doi.org/10.1109/35.689634 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061159636
    176 rdf:type schema:CreativeWork
    177 https://doi.org/10.1109/70.105395 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061215884
    178 rdf:type schema:CreativeWork
    179 https://doi.org/10.1109/icdcs.2000.840953 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094334627
    180 rdf:type schema:CreativeWork
    181 https://doi.org/10.1109/icdcs.2003.1203510 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093976351
    182 rdf:type schema:CreativeWork
    183 https://doi.org/10.1109/isads.1999.838454 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095053032
    184 rdf:type schema:CreativeWork
    185 https://doi.org/10.1109/sfcs.1978.30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086207665
    186 rdf:type schema:CreativeWork
    187 https://doi.org/10.1109/sfcs.1994.365703 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093260501
    188 rdf:type schema:CreativeWork
    189 https://doi.org/10.1137/0207017 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841411
    190 rdf:type schema:CreativeWork
    191 https://doi.org/10.1137/s0097539700377293 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879258
    192 rdf:type schema:CreativeWork
    193 https://doi.org/10.1137/s0097539791194931 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879656
    194 rdf:type schema:CreativeWork
    195 https://doi.org/10.1137/s009753979732428x schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880193
    196 rdf:type schema:CreativeWork
    197 https://doi.org/10.1145/274787.274788 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010783463
    198 rdf:type schema:CreativeWork
    199 https://doi.org/10.1145/276698.276759 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022410991
    200 rdf:type schema:CreativeWork
    201 https://doi.org/10.1145/564870.564906 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051619886
    202 rdf:type schema:CreativeWork
    203 https://doi.org/10.1145/777412.777469 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043112318
    204 rdf:type schema:CreativeWork
    205 https://doi.org/10.1239/jap/1032374243 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064441573
    206 rdf:type schema:CreativeWork
    207 https://www.grid.ac/institutes/grid.28046.38 schema:alternateName University of Ottawa
    208 schema:name School of Information Technology and Engineering, University of Ottawa, Ottawa, Canada
    209 rdf:type schema:Organization
    210 https://www.grid.ac/institutes/grid.34428.39 schema:alternateName Carleton University
    211 schema:name School of Computer Science, Carleton University, Ottawa, Ontario, Canada
    212 rdf:type schema:Organization
    213 https://www.grid.ac/institutes/grid.5395.a schema:alternateName University of Pisa
    214 schema:name Dipartimento di Informatica, Università di Pisa, Italy
    215 rdf:type schema:Organization
     




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


    ...