Intruder Capture in Sierpiński Graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2007

AUTHORS

Flaminia L. Luccio

ABSTRACT

In this paper we consider the problem of capturing an intruder in a networked environment. The intruder is defined as a mobile entity that moves arbitrarily fast inside the network and escapes from a team of software agents. The agents have to collaborate and coordinate their moves in order to isolate the intruder. They move asynchronously and they know the network topology they are in is a particular fractal graph, the Sierpiński graph SG n . We first derive lower bounds on the minimum number of agents, number of moves and time steps required to capture the intruder. We then consider two models: one in which agents have a capability, of “seeing” the state of their neighbors; the second one in which the actions of the agents are leaded by a coordinator. One of our goals is to continue a previous study on what is the impact of visibility on complexity: we have found that in this topology the visibility assumption allows us to reach an optimal bound on the number of agents required for the cleaning strategy. On the other hand, the second strategy relies only on local computations but requires an extra agent and a higher (by a constant) complexity in terms of time and number of moves. More... »

PAGES

249-261

References to SciGraph publications

  • 2006. Distributed Chasing of Network Intruders in STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY
  • 2005. Cleaning an Arbitrary Regular Network with Mobile Agents in DISTRIBUTED COMPUTING AND INTERNET TECHNOLOGY
  • Book

    TITLE

    Fun with Algorithms

    ISBN

    978-3-540-72913-6

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-72914-3_22

    DOI

    http://dx.doi.org/10.1007/978-3-540-72914-3_22

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "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": "Ca Foscari University of Venice", 
              "id": "https://www.grid.ac/institutes/grid.7240.1", 
              "name": [
                "Dipartimento di Informatica, Universit\u00e0 Ca\u2019 Foscari Venezia, Venice, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Luccio", 
            "givenName": "Flaminia L.", 
            "id": "sg:person.011224036615.55", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011224036615.55"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/11780823_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007989748", 
              "https://doi.org/10.1007/11780823_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11780823_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007989748", 
              "https://doi.org/10.1007/11780823_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/151261.151263", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017456454"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(86)90146-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023492229"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(86)90146-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023492229"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11604655_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024913177", 
              "https://doi.org/10.1007/11604655_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/inco.1994.1064", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037418865"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/42267.42268", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045068727"
            ], 
            "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/ipdps.2006.1639545", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094086841"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/ipdps.2005.151", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095757918"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2007", 
        "datePublishedReg": "2007-01-01", 
        "description": "In this paper we consider the problem of capturing an intruder in a networked environment. The intruder is defined as a mobile entity that moves arbitrarily fast inside the network and escapes from a team of software agents. The agents have to collaborate and coordinate their moves in order to isolate the intruder. They move asynchronously and they know the network topology they are in is a particular fractal graph, the Sierpi\u0144ski graph SG n . We first derive lower bounds on the minimum number of agents, number of moves and time steps required to capture the intruder. We then consider two models: one in which agents have a capability, of \u201cseeing\u201d the state of their neighbors; the second one in which the actions of the agents are leaded by a coordinator. One of our goals is to continue a previous study on what is the impact of visibility on complexity: we have found that in this topology the visibility assumption allows us to reach an optimal bound on the number of agents required for the cleaning strategy. On the other hand, the second strategy relies only on local computations but requires an extra agent and a higher (by a constant) complexity in terms of time and number of moves.", 
        "editor": [
          {
            "familyName": "Crescenzi", 
            "givenName": "Pierluigi", 
            "type": "Person"
          }, 
          {
            "familyName": "Prencipe", 
            "givenName": "Giuseppe", 
            "type": "Person"
          }, 
          {
            "familyName": "Pucci", 
            "givenName": "Geppino", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-72914-3_22", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-72913-6"
          ], 
          "name": "Fun with Algorithms", 
          "type": "Book"
        }, 
        "name": "Intruder Capture in Sierpi\u0144ski Graphs", 
        "pagination": "249-261", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-72914-3_22"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "05a1749f1e352d9e0aac18164b22b917afd77c07665ffceec589fa9e90fb283d"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1001182013"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-72914-3_22", 
          "https://app.dimensions.ai/details/publication/pub.1001182013"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T16:13", 
        "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_00000243.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-540-72914-3_22"
      }
    ]
     

    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/978-3-540-72914-3_22'

    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/978-3-540-72914-3_22'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-72914-3_22'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-72914-3_22'


     

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

    103 TRIPLES      23 PREDICATES      36 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-72914-3_22 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Ne0df5b311db64fbea81fed2e12bb0cb1
    4 schema:citation sg:pub.10.1007/11604655_17
    5 sg:pub.10.1007/11780823_7
    6 https://doi.org/10.1006/inco.1994.1064
    7 https://doi.org/10.1016/0304-3975(86)90146-5
    8 https://doi.org/10.1109/ipdps.2005.151
    9 https://doi.org/10.1109/ipdps.2006.1639545
    10 https://doi.org/10.1145/151261.151263
    11 https://doi.org/10.1145/42267.42268
    12 https://doi.org/10.1145/564870.564906
    13 schema:datePublished 2007
    14 schema:datePublishedReg 2007-01-01
    15 schema:description In this paper we consider the problem of capturing an intruder in a networked environment. The intruder is defined as a mobile entity that moves arbitrarily fast inside the network and escapes from a team of software agents. The agents have to collaborate and coordinate their moves in order to isolate the intruder. They move asynchronously and they know the network topology they are in is a particular fractal graph, the Sierpiński graph SG n . We first derive lower bounds on the minimum number of agents, number of moves and time steps required to capture the intruder. We then consider two models: one in which agents have a capability, of “seeing” the state of their neighbors; the second one in which the actions of the agents are leaded by a coordinator. One of our goals is to continue a previous study on what is the impact of visibility on complexity: we have found that in this topology the visibility assumption allows us to reach an optimal bound on the number of agents required for the cleaning strategy. On the other hand, the second strategy relies only on local computations but requires an extra agent and a higher (by a constant) complexity in terms of time and number of moves.
    16 schema:editor N521319c8c782457b99f5dff74d3a288e
    17 schema:genre chapter
    18 schema:inLanguage en
    19 schema:isAccessibleForFree false
    20 schema:isPartOf N530fe461a3dd4f88955196fcab5045e4
    21 schema:name Intruder Capture in Sierpiński Graphs
    22 schema:pagination 249-261
    23 schema:productId N4765c2a06dc942da81812d81637dc8f8
    24 N9c89f7a623c94f7aa638461b8a15d088
    25 Nea9683b16c2242cfa295759cb9106d28
    26 schema:publisher N7bb3385f594e48f38c5eea80cece8da4
    27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001182013
    28 https://doi.org/10.1007/978-3-540-72914-3_22
    29 schema:sdDatePublished 2019-04-15T16:13
    30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    31 schema:sdPublisher Na037c02168fc45ea8e0be359a824a8eb
    32 schema:url http://link.springer.com/10.1007/978-3-540-72914-3_22
    33 sgo:license sg:explorer/license/
    34 sgo:sdDataset chapters
    35 rdf:type schema:Chapter
    36 N456f90f39fce401f97b19758d0e55ad7 schema:familyName Crescenzi
    37 schema:givenName Pierluigi
    38 rdf:type schema:Person
    39 N4765c2a06dc942da81812d81637dc8f8 schema:name doi
    40 schema:value 10.1007/978-3-540-72914-3_22
    41 rdf:type schema:PropertyValue
    42 N521319c8c782457b99f5dff74d3a288e rdf:first N456f90f39fce401f97b19758d0e55ad7
    43 rdf:rest N6030acda4c884a0d82b4872ca0b576b6
    44 N530fe461a3dd4f88955196fcab5045e4 schema:isbn 978-3-540-72913-6
    45 schema:name Fun with Algorithms
    46 rdf:type schema:Book
    47 N53e8a6eac550405588a9b4ab7aab8f84 rdf:first Na8d8c44e47bf495c926b8ec16e1a635e
    48 rdf:rest rdf:nil
    49 N6030acda4c884a0d82b4872ca0b576b6 rdf:first N8e91f00646374d1ca9b1bcb5864cab7f
    50 rdf:rest N53e8a6eac550405588a9b4ab7aab8f84
    51 N7bb3385f594e48f38c5eea80cece8da4 schema:location Berlin, Heidelberg
    52 schema:name Springer Berlin Heidelberg
    53 rdf:type schema:Organisation
    54 N8e91f00646374d1ca9b1bcb5864cab7f schema:familyName Prencipe
    55 schema:givenName Giuseppe
    56 rdf:type schema:Person
    57 N9c89f7a623c94f7aa638461b8a15d088 schema:name readcube_id
    58 schema:value 05a1749f1e352d9e0aac18164b22b917afd77c07665ffceec589fa9e90fb283d
    59 rdf:type schema:PropertyValue
    60 Na037c02168fc45ea8e0be359a824a8eb schema:name Springer Nature - SN SciGraph project
    61 rdf:type schema:Organization
    62 Na8d8c44e47bf495c926b8ec16e1a635e schema:familyName Pucci
    63 schema:givenName Geppino
    64 rdf:type schema:Person
    65 Ne0df5b311db64fbea81fed2e12bb0cb1 rdf:first sg:person.011224036615.55
    66 rdf:rest rdf:nil
    67 Nea9683b16c2242cfa295759cb9106d28 schema:name dimensions_id
    68 schema:value pub.1001182013
    69 rdf:type schema:PropertyValue
    70 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    71 schema:name Information and Computing Sciences
    72 rdf:type schema:DefinedTerm
    73 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    74 schema:name Computation Theory and Mathematics
    75 rdf:type schema:DefinedTerm
    76 sg:person.011224036615.55 schema:affiliation https://www.grid.ac/institutes/grid.7240.1
    77 schema:familyName Luccio
    78 schema:givenName Flaminia L.
    79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011224036615.55
    80 rdf:type schema:Person
    81 sg:pub.10.1007/11604655_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024913177
    82 https://doi.org/10.1007/11604655_17
    83 rdf:type schema:CreativeWork
    84 sg:pub.10.1007/11780823_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007989748
    85 https://doi.org/10.1007/11780823_7
    86 rdf:type schema:CreativeWork
    87 https://doi.org/10.1006/inco.1994.1064 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037418865
    88 rdf:type schema:CreativeWork
    89 https://doi.org/10.1016/0304-3975(86)90146-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023492229
    90 rdf:type schema:CreativeWork
    91 https://doi.org/10.1109/ipdps.2005.151 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095757918
    92 rdf:type schema:CreativeWork
    93 https://doi.org/10.1109/ipdps.2006.1639545 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094086841
    94 rdf:type schema:CreativeWork
    95 https://doi.org/10.1145/151261.151263 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017456454
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1145/42267.42268 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045068727
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1145/564870.564906 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051619886
    100 rdf:type schema:CreativeWork
    101 https://www.grid.ac/institutes/grid.7240.1 schema:alternateName Ca Foscari University of Venice
    102 schema:name Dipartimento di Informatica, Università Ca’ Foscari Venezia, Venice, Italy
    103 rdf:type schema:Organization
     




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


    ...