Contiguous Search Problem in Sierpiński Graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2009-02

AUTHORS

Flaminia L. Luccio

ABSTRACT

In this paper we consider the problem of capturing an intruder in a particular fractal graph, the Sierpiński graph SGn. The problem consists of having a team of mobile software agents that collaborate in order to capture the intruder. The intruder is a mobile entity that escapes from the team of agents, moving arbitrarily fast inside the network, i.e., traversing any number of contiguous nodes as long as no other agent resides on them. The agents move asynchronously and they know the network topology they are in is a Sierpiński graph SGn. 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 some variations of the model based on the capabilities of the agents: visibility, where the agents can “see” the state of their neighbors and thus can move autonomously; locality, where the agents can only access local information and thus their moves have to be coordinated by a leader. For each model, we design a capturing strategy and we make some observations. One of our goals is to continue a previous study on what is the impact of visibility on complexity: in this topology we are able to reach an optimal bound on the number of agents required by both cleaning strategies. However, the strategy in the visibility model is fully distributed, whereas the other strategy requires a leader. Moreover, the second strategy requires a higher number of moves and time steps. More... »

PAGES

186-204

References to SciGraph publications

  • 2006. Distributed Chasing of Network Intruders in STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY
  • 2006. Connected Treewidth and Connected Graph Searching in LATIN 2006: THEORETICAL INFORMATICS
  • 2007. Intruder Capture in Sierpiński Graphs in FUN WITH ALGORITHMS
  • 2004. Sweeping Graphs with Large Clique Number in ALGORITHMS AND COMPUTATION
  • 2005. Cleaning an Arbitrary Regular Network with Mobile Agents in DISTRIBUTED COMPUTING AND INTERNET TECHNOLOGY
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00224-008-9116-z

    DOI

    http://dx.doi.org/10.1007/s00224-008-9116-z

    DIMENSIONS

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


    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, via Torino 155, 30172, 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/978-3-540-72914-3_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001182013", 
              "https://doi.org/10.1007/978-3-540-72914-3_22"
            ], 
            "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": "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": "sg:pub.10.1007/978-3-540-30551-4_77", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020618149", 
              "https://doi.org/10.1007/978-3-540-30551-4_77"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30551-4_77", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020618149", 
              "https://doi.org/10.1007/978-3-540-30551-4_77"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0196-6774(86)90023-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021500239"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11682462_45", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022989737", 
              "https://doi.org/10.1007/11682462_45"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11682462_45", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022989737", 
              "https://doi.org/10.1007/11682462_45"
            ], 
            "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.1016/s0304-3975(96)00177-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029676660"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0196-6774(91)90003-h", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033945460"
            ], 
            "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.1016/s1389-1286(00)00136-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042137193"
            ], 
            "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.1016/0095-8956(83)90079-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049646665"
            ], 
            "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.1088/0305-4470/39/38/003", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1059079854"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1142/s0129054107004838", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062896776"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/ipdps.2005.151", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095757918"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2009-02", 
        "datePublishedReg": "2009-02-01", 
        "description": "In this paper we consider the problem of capturing an intruder in a particular fractal graph, the Sierpi\u0144ski graph SGn. The problem consists of having a team of mobile software agents that collaborate in order to capture the intruder. The intruder is a mobile entity that escapes from the team of agents, moving arbitrarily fast inside the network, i.e., traversing any number of contiguous nodes as long as no other agent resides on them. The agents move asynchronously and they know the network topology they are in is a Sierpi\u0144ski graph SGn. 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 some variations of the model based on the capabilities of the agents: visibility, where the agents can \u201csee\u201d the state of their neighbors and thus can move autonomously; locality, where the agents can only access local information and thus their moves have to be coordinated by a leader. For each model, we design a capturing strategy and we make some observations. One of our goals is to continue a previous study on what is the impact of visibility on complexity: in this topology we are able to reach an optimal bound on the number of agents required by both cleaning strategies. However, the strategy in the visibility model is fully distributed, whereas the other strategy requires a leader. Moreover, the second strategy requires a higher number of moves and time steps.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00224-008-9116-z", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1052098", 
            "issn": [
              "1432-4350", 
              "1433-0490"
            ], 
            "name": "Theory of Computing Systems", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "44"
          }
        ], 
        "name": "Contiguous Search Problem in Sierpi\u0144ski Graphs", 
        "pagination": "186-204", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "5c7d5428ab6aea16b189106e8b67769b318233d42ec61d0e1cc1293dff1807a2"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00224-008-9116-z"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1019411622"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00224-008-9116-z", 
          "https://app.dimensions.ai/details/publication/pub.1019411622"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T14:32", 
        "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/0000000373_0000000373/records_13099_00000000.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/s00224-008-9116-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/s00224-008-9116-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/s00224-008-9116-z'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-008-9116-z'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-008-9116-z'


     

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

    120 TRIPLES      21 PREDICATES      45 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00224-008-9116-z schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Nd1ee5ae825a94653b09dd2309fc79b53
    4 schema:citation sg:pub.10.1007/11604655_17
    5 sg:pub.10.1007/11682462_45
    6 sg:pub.10.1007/11780823_7
    7 sg:pub.10.1007/978-3-540-30551-4_77
    8 sg:pub.10.1007/978-3-540-72914-3_22
    9 https://doi.org/10.1006/inco.1994.1064
    10 https://doi.org/10.1016/0095-8956(83)90079-5
    11 https://doi.org/10.1016/0196-6774(86)90023-4
    12 https://doi.org/10.1016/0196-6774(91)90003-h
    13 https://doi.org/10.1016/0304-3975(86)90146-5
    14 https://doi.org/10.1016/s0304-3975(96)00177-6
    15 https://doi.org/10.1016/s1389-1286(00)00136-5
    16 https://doi.org/10.1088/0305-4470/39/38/003
    17 https://doi.org/10.1109/ipdps.2005.151
    18 https://doi.org/10.1142/s0129054107004838
    19 https://doi.org/10.1145/151261.151263
    20 https://doi.org/10.1145/42267.42268
    21 https://doi.org/10.1145/564870.564906
    22 schema:datePublished 2009-02
    23 schema:datePublishedReg 2009-02-01
    24 schema:description In this paper we consider the problem of capturing an intruder in a particular fractal graph, the Sierpiński graph SGn. The problem consists of having a team of mobile software agents that collaborate in order to capture the intruder. The intruder is a mobile entity that escapes from the team of agents, moving arbitrarily fast inside the network, i.e., traversing any number of contiguous nodes as long as no other agent resides on them. The agents move asynchronously and they know the network topology they are in is a Sierpiński graph SGn. 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 some variations of the model based on the capabilities of the agents: visibility, where the agents can “see” the state of their neighbors and thus can move autonomously; locality, where the agents can only access local information and thus their moves have to be coordinated by a leader. For each model, we design a capturing strategy and we make some observations. One of our goals is to continue a previous study on what is the impact of visibility on complexity: in this topology we are able to reach an optimal bound on the number of agents required by both cleaning strategies. However, the strategy in the visibility model is fully distributed, whereas the other strategy requires a leader. Moreover, the second strategy requires a higher number of moves and time steps.
    25 schema:genre research_article
    26 schema:inLanguage en
    27 schema:isAccessibleForFree false
    28 schema:isPartOf N7ac7254c94604afb9f0b37d054d3b418
    29 Nbc06e968c35c45a1be8c468f57f8e89e
    30 sg:journal.1052098
    31 schema:name Contiguous Search Problem in Sierpiński Graphs
    32 schema:pagination 186-204
    33 schema:productId N1fdad26641c6400b9215ab4f5403d021
    34 N60c22ab0b072487ea3bc69091c2d1749
    35 Nae1b409820fa4f78bb93ef5f4093e838
    36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019411622
    37 https://doi.org/10.1007/s00224-008-9116-z
    38 schema:sdDatePublished 2019-04-11T14:32
    39 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    40 schema:sdPublisher Na6620c597bc44b06b8aef8aebac834bf
    41 schema:url http://link.springer.com/10.1007/s00224-008-9116-z
    42 sgo:license sg:explorer/license/
    43 sgo:sdDataset articles
    44 rdf:type schema:ScholarlyArticle
    45 N1fdad26641c6400b9215ab4f5403d021 schema:name dimensions_id
    46 schema:value pub.1019411622
    47 rdf:type schema:PropertyValue
    48 N60c22ab0b072487ea3bc69091c2d1749 schema:name doi
    49 schema:value 10.1007/s00224-008-9116-z
    50 rdf:type schema:PropertyValue
    51 N7ac7254c94604afb9f0b37d054d3b418 schema:volumeNumber 44
    52 rdf:type schema:PublicationVolume
    53 Na6620c597bc44b06b8aef8aebac834bf schema:name Springer Nature - SN SciGraph project
    54 rdf:type schema:Organization
    55 Nae1b409820fa4f78bb93ef5f4093e838 schema:name readcube_id
    56 schema:value 5c7d5428ab6aea16b189106e8b67769b318233d42ec61d0e1cc1293dff1807a2
    57 rdf:type schema:PropertyValue
    58 Nbc06e968c35c45a1be8c468f57f8e89e schema:issueNumber 2
    59 rdf:type schema:PublicationIssue
    60 Nd1ee5ae825a94653b09dd2309fc79b53 rdf:first sg:person.011224036615.55
    61 rdf:rest rdf:nil
    62 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    63 schema:name Information and Computing Sciences
    64 rdf:type schema:DefinedTerm
    65 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    66 schema:name Computation Theory and Mathematics
    67 rdf:type schema:DefinedTerm
    68 sg:journal.1052098 schema:issn 1432-4350
    69 1433-0490
    70 schema:name Theory of Computing Systems
    71 rdf:type schema:Periodical
    72 sg:person.011224036615.55 schema:affiliation https://www.grid.ac/institutes/grid.7240.1
    73 schema:familyName Luccio
    74 schema:givenName Flaminia L.
    75 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011224036615.55
    76 rdf:type schema:Person
    77 sg:pub.10.1007/11604655_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024913177
    78 https://doi.org/10.1007/11604655_17
    79 rdf:type schema:CreativeWork
    80 sg:pub.10.1007/11682462_45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022989737
    81 https://doi.org/10.1007/11682462_45
    82 rdf:type schema:CreativeWork
    83 sg:pub.10.1007/11780823_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007989748
    84 https://doi.org/10.1007/11780823_7
    85 rdf:type schema:CreativeWork
    86 sg:pub.10.1007/978-3-540-30551-4_77 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020618149
    87 https://doi.org/10.1007/978-3-540-30551-4_77
    88 rdf:type schema:CreativeWork
    89 sg:pub.10.1007/978-3-540-72914-3_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001182013
    90 https://doi.org/10.1007/978-3-540-72914-3_22
    91 rdf:type schema:CreativeWork
    92 https://doi.org/10.1006/inco.1994.1064 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037418865
    93 rdf:type schema:CreativeWork
    94 https://doi.org/10.1016/0095-8956(83)90079-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049646665
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1016/0196-6774(86)90023-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021500239
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1016/0196-6774(91)90003-h schema:sameAs https://app.dimensions.ai/details/publication/pub.1033945460
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1016/0304-3975(86)90146-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023492229
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1016/s0304-3975(96)00177-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029676660
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1016/s1389-1286(00)00136-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042137193
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1088/0305-4470/39/38/003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059079854
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1109/ipdps.2005.151 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095757918
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1142/s0129054107004838 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062896776
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1145/151261.151263 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017456454
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.1145/42267.42268 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045068727
    115 rdf:type schema:CreativeWork
    116 https://doi.org/10.1145/564870.564906 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051619886
    117 rdf:type schema:CreativeWork
    118 https://www.grid.ac/institutes/grid.7240.1 schema:alternateName Ca Foscari University of Venice
    119 schema:name Dipartimento di Informatica, Università Ca’ Foscari Venezia, via Torino 155, 30172, Venice, Italy
    120 rdf:type schema:Organization
     




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


    ...