Improving the Optimal Bounds for Black Hole Search in Rings View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2011

AUTHORS

Balasingham Balamohan , Paola Flocchini , Ali Miri , Nicola Santoro

ABSTRACT

In this paper we re-examine the well known problem of asynchronous black hole search in a ring. It is well known that at least 2 agents are needed and the total number of agents’ moves is at least Ω(n logn); solutions indeed exist that allow a team of two agents to locate the black hole with the asymptotically optimal cost of Θ(n logn) moves. In this paper we first of all determine the exact move complexity of black hole search in an asynchronous ring. In fact, we prove that 3nlog3n − O(n) moves are necessary. We then present a novel algorithm that allows two agents to locate the black hole with at most 3nlog3n + O(n) moves, improving the existing upper bounds, and matching the lower bound up to the constant of proportionality. Finally we show how to modify the protocol so to achieve asymptotically optimal time complexity Θ(n), still with 3nlog3n + O(n) moves; this improves upon all existing time-optimal protocols, which require O(n2) moves. This protocol is the first that is optimal with respect to all three complexity measures: size (number of agents), cost (number of moves) and time; in particular, its cost and size complexities match the lower bounds up to the constant. More... »

PAGES

198-209

References to SciGraph publications

  • 2006. Exploring an Unknown Graph to Locate a Black Hole Using Tokens in FOURTH IFIP INTERNATIONAL CONFERENCE ON THEORETICAL COMPUTER SCIENCE- TCS 2006
  • 2010. Periodic Data Retrieval Problem in Rings Containing a Malicious Host in STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY
  • 2010. Black Hole Search in Directed Graphs in STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY
  • 2006. Black Hole Search in Asynchronous Rings Using Tokens in ALGORITHMS AND COMPLEXITY
  • 2009. Locating a Black Hole without the Knowledge of Incoming Link in ALGORITHMIC ASPECTS OF WIRELESS SENSOR NETWORKS
  • 2007-05. Mobile Search for a Black Hole in an Anonymous Ring in ALGORITHMICA
  • 2012-04. Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pebbles in ALGORITHMICA
  • 2006. Searching for Black-Hole Faults in a Network Using Multiple Agents in PRINCIPLES OF DISTRIBUTED SYSTEMS
  • 2009. Black Hole Search with Tokens in Interconnected Networks in STABILIZATION, SAFETY, AND SECURITY OF DISTRIBUTED SYSTEMS
  • 2009. Synchronization Helps Robots to Detect Black Holes in Directed Graphs in PRINCIPLES OF DISTRIBUTED SYSTEMS
  • 2004. Improved Bounds for Optimal Black Hole Search with a Network Map in STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY
  • 2006-09. Searching for a black hole in arbitrary networks: optimal mobile agents protocols in DISTRIBUTED COMPUTING
  • 2007. Rendezvous of Mobile Agents in Unknown Graphs with Faulty Links in DISTRIBUTED COMPUTING
  • 2010. Time Optimal Algorithms for Black Hole Search in Rings in COMBINATORIAL OPTIMIZATION AND APPLICATIONS
  • Book

    TITLE

    Structural Information and Communication Complexity

    ISBN

    978-3-642-22211-5
    978-3-642-22212-2

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-22212-2_18

    DOI

    http://dx.doi.org/10.1007/978-3-642-22212-2_18

    DIMENSIONS

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


    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": "University of Ottawa", 
              "id": "https://www.grid.ac/institutes/grid.28046.38", 
              "name": [
                "University of Ottawa, Ottawa, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Balamohan", 
            "givenName": "Balasingham", 
            "id": "sg:person.01127513656.68", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01127513656.68"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Ottawa", 
              "id": "https://www.grid.ac/institutes/grid.28046.38", 
              "name": [
                "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": "Ryerson University", 
              "id": "https://www.grid.ac/institutes/grid.68312.3e", 
              "name": [
                "Ryerson University, Toronto, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Miri", 
            "givenName": "Ali", 
            "id": "sg:person.011073450025.09", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011073450025.09"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Carleton University", 
              "id": "https://www.grid.ac/institutes/grid.34428.39", 
              "name": [
                "Carleton University, Ottawa, 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/s00446-006-0154-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000916693", 
              "https://doi.org/10.1007/s00446-006-0154-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00446-006-0154-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000916693", 
              "https://doi.org/10.1007/s00446-006-0154-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2007.04.024", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006130162"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/net.20095", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015469195"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/net.20095", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015469195"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-05118-0_46", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016037775", 
              "https://doi.org/10.1007/978-3-642-05118-0_46"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-05118-0_46", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016037775", 
              "https://doi.org/10.1007/978-3-642-05118-0_46"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-05434-1_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017113003", 
              "https://doi.org/10.1007/978-3-642-05434-1_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-05434-1_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017113003", 
              "https://doi.org/10.1007/978-3-642-05434-1_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-27796-5_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022687220", 
              "https://doi.org/10.1007/978-3-540-27796-5_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-27796-5_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022687220", 
              "https://doi.org/10.1007/978-3-540-27796-5_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-13284-1_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023550915", 
              "https://doi.org/10.1007/978-3-642-13284-1_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-13284-1_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023550915", 
              "https://doi.org/10.1007/978-3-642-13284-1_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00453-006-1232-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027520360", 
              "https://doi.org/10.1007/s00453-006-1232-z"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/net.20233", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028617841"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-0-387-34735-6_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030142924", 
              "https://doi.org/10.1007/978-0-387-34735-6_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-10877-8_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031426893", 
              "https://doi.org/10.1007/978-3-642-10877-8_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-10877-8_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031426893", 
              "https://doi.org/10.1007/978-3-642-10877-8_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11758471_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031542158", 
              "https://doi.org/10.1007/11758471_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11758471_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031542158", 
              "https://doi.org/10.1007/11758471_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-75142-7_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032317348", 
              "https://doi.org/10.1007/978-3-540-75142-7_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-75142-7_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032317348", 
              "https://doi.org/10.1007/978-3-540-75142-7_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00453-011-9496-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033084507", 
              "https://doi.org/10.1007/s00453-011-9496-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-17461-2_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033209134", 
              "https://doi.org/10.1007/978-3-642-17461-2_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-17461-2_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033209134", 
              "https://doi.org/10.1007/978-3-642-17461-2_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-11476-2_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033891893", 
              "https://doi.org/10.1007/978-3-642-11476-2_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-11476-2_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033891893", 
              "https://doi.org/10.1007/978-3-642-11476-2_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2010.01.011", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038583630"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s0963548306008133", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045829097"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11945529_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047952182", 
              "https://doi.org/10.1007/11945529_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11945529_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047952182", 
              "https://doi.org/10.1007/11945529_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/ipdps.2009.5161080", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093705627"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2011", 
        "datePublishedReg": "2011-01-01", 
        "description": "In this paper we re-examine the well known problem of asynchronous black hole search in a ring. It is well known that at least 2 agents are needed and the total number of agents\u2019 moves is at least \u03a9(n logn); solutions indeed exist that allow a team of two agents to locate the black hole with the asymptotically optimal cost of \u0398(n logn) moves. In this paper we first of all determine the exact move complexity of black hole search in an asynchronous ring. In fact, we prove that 3nlog3n \u2212 O(n) moves are necessary. We then present a novel algorithm that allows two agents to locate the black hole with at most 3nlog3n + O(n) moves, improving the existing upper bounds, and matching the lower bound up to the constant of proportionality. Finally we show how to modify the protocol so to achieve asymptotically optimal time complexity \u0398(n), still with 3nlog3n + O(n) moves; this improves upon all existing time-optimal protocols, which require O(n2) moves. This protocol is the first that is optimal with respect to all three complexity measures: size (number of agents), cost (number of moves) and time; in particular, its cost and size complexities match the lower bounds up to the constant.", 
        "editor": [
          {
            "familyName": "Kosowski", 
            "givenName": "Adrian", 
            "type": "Person"
          }, 
          {
            "familyName": "Yamashita", 
            "givenName": "Masafumi", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-22212-2_18", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-642-22211-5", 
            "978-3-642-22212-2"
          ], 
          "name": "Structural Information and Communication Complexity", 
          "type": "Book"
        }, 
        "name": "Improving the Optimal Bounds for Black Hole Search in Rings", 
        "pagination": "198-209", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1014672497"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-22212-2_18"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "45e725271ef7030aa1ce7a7ff18efbd4e95a25ab4be4465c7f6ddca4ffe774c4"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-22212-2_18", 
          "https://app.dimensions.ai/details/publication/pub.1014672497"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T08:59", 
        "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/0000000369_0000000369/records_68984_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-642-22212-2_18"
      }
    ]
     

    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-642-22212-2_18'

    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-642-22212-2_18'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22212-2_18'

    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-642-22212-2_18'


     

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

    171 TRIPLES      23 PREDICATES      47 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-22212-2_18 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N34f62833b64245459aa8a7f2d078a055
    4 schema:citation sg:pub.10.1007/11758471_16
    5 sg:pub.10.1007/11945529_23
    6 sg:pub.10.1007/978-0-387-34735-6_14
    7 sg:pub.10.1007/978-3-540-27796-5_11
    8 sg:pub.10.1007/978-3-540-75142-7_11
    9 sg:pub.10.1007/978-3-642-05118-0_46
    10 sg:pub.10.1007/978-3-642-05434-1_13
    11 sg:pub.10.1007/978-3-642-10877-8_9
    12 sg:pub.10.1007/978-3-642-11476-2_15
    13 sg:pub.10.1007/978-3-642-13284-1_13
    14 sg:pub.10.1007/978-3-642-17461-2_5
    15 sg:pub.10.1007/s00446-006-0154-y
    16 sg:pub.10.1007/s00453-006-1232-z
    17 sg:pub.10.1007/s00453-011-9496-3
    18 https://doi.org/10.1002/net.20095
    19 https://doi.org/10.1002/net.20233
    20 https://doi.org/10.1016/j.tcs.2007.04.024
    21 https://doi.org/10.1016/j.tcs.2010.01.011
    22 https://doi.org/10.1017/s0963548306008133
    23 https://doi.org/10.1109/ipdps.2009.5161080
    24 schema:datePublished 2011
    25 schema:datePublishedReg 2011-01-01
    26 schema:description In this paper we re-examine the well known problem of asynchronous black hole search in a ring. It is well known that at least 2 agents are needed and the total number of agents’ moves is at least Ω(n logn); solutions indeed exist that allow a team of two agents to locate the black hole with the asymptotically optimal cost of Θ(n logn) moves. In this paper we first of all determine the exact move complexity of black hole search in an asynchronous ring. In fact, we prove that 3nlog3n − O(n) moves are necessary. We then present a novel algorithm that allows two agents to locate the black hole with at most 3nlog3n + O(n) moves, improving the existing upper bounds, and matching the lower bound up to the constant of proportionality. Finally we show how to modify the protocol so to achieve asymptotically optimal time complexity Θ(n), still with 3nlog3n + O(n) moves; this improves upon all existing time-optimal protocols, which require O(n2) moves. This protocol is the first that is optimal with respect to all three complexity measures: size (number of agents), cost (number of moves) and time; in particular, its cost and size complexities match the lower bounds up to the constant.
    27 schema:editor N00da81764dc04d1c986d60ddefff0d4a
    28 schema:genre chapter
    29 schema:inLanguage en
    30 schema:isAccessibleForFree false
    31 schema:isPartOf Nab04f0dba5c64344b0c1e7e2cf78dacc
    32 schema:name Improving the Optimal Bounds for Black Hole Search in Rings
    33 schema:pagination 198-209
    34 schema:productId N7f9eccc208d343e48087bdc93bf612db
    35 Na1997bda684d4abf9779fc5020406250
    36 Nb27716dd1adf4ebfaa093c1eac0d12ee
    37 schema:publisher N7e922111fdf54f0f81b7fd66d0bd85cd
    38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014672497
    39 https://doi.org/10.1007/978-3-642-22212-2_18
    40 schema:sdDatePublished 2019-04-16T08:59
    41 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    42 schema:sdPublisher N9f98fdb098b04614bf95304ea92ac02a
    43 schema:url https://link.springer.com/10.1007%2F978-3-642-22212-2_18
    44 sgo:license sg:explorer/license/
    45 sgo:sdDataset chapters
    46 rdf:type schema:Chapter
    47 N00da81764dc04d1c986d60ddefff0d4a rdf:first N9f9281e92fce47f8a0586848cf6318bb
    48 rdf:rest N100ad1d80b8e47aca96e5fd06aeb3c70
    49 N100ad1d80b8e47aca96e5fd06aeb3c70 rdf:first N9562b4e668f04750a037b91e00c50c6a
    50 rdf:rest rdf:nil
    51 N34f62833b64245459aa8a7f2d078a055 rdf:first sg:person.01127513656.68
    52 rdf:rest N7a4182d8b64e49c39eefb53449cde65b
    53 N7a4182d8b64e49c39eefb53449cde65b rdf:first sg:person.011601470625.25
    54 rdf:rest Na2a939f18ef849b395c9901ecd0b0f5b
    55 N7e922111fdf54f0f81b7fd66d0bd85cd schema:location Berlin, Heidelberg
    56 schema:name Springer Berlin Heidelberg
    57 rdf:type schema:Organisation
    58 N7f9eccc208d343e48087bdc93bf612db schema:name readcube_id
    59 schema:value 45e725271ef7030aa1ce7a7ff18efbd4e95a25ab4be4465c7f6ddca4ffe774c4
    60 rdf:type schema:PropertyValue
    61 N9562b4e668f04750a037b91e00c50c6a schema:familyName Yamashita
    62 schema:givenName Masafumi
    63 rdf:type schema:Person
    64 N9f9281e92fce47f8a0586848cf6318bb schema:familyName Kosowski
    65 schema:givenName Adrian
    66 rdf:type schema:Person
    67 N9f98fdb098b04614bf95304ea92ac02a schema:name Springer Nature - SN SciGraph project
    68 rdf:type schema:Organization
    69 Na1997bda684d4abf9779fc5020406250 schema:name dimensions_id
    70 schema:value pub.1014672497
    71 rdf:type schema:PropertyValue
    72 Na2a939f18ef849b395c9901ecd0b0f5b rdf:first sg:person.011073450025.09
    73 rdf:rest Nc04a7459cbd44fdb82b64f36cbdeaa3d
    74 Nab04f0dba5c64344b0c1e7e2cf78dacc schema:isbn 978-3-642-22211-5
    75 978-3-642-22212-2
    76 schema:name Structural Information and Communication Complexity
    77 rdf:type schema:Book
    78 Nb27716dd1adf4ebfaa093c1eac0d12ee schema:name doi
    79 schema:value 10.1007/978-3-642-22212-2_18
    80 rdf:type schema:PropertyValue
    81 Nc04a7459cbd44fdb82b64f36cbdeaa3d rdf:first sg:person.010566557723.84
    82 rdf:rest rdf:nil
    83 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    84 schema:name Information and Computing Sciences
    85 rdf:type schema:DefinedTerm
    86 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    87 schema:name Computation Theory and Mathematics
    88 rdf:type schema:DefinedTerm
    89 sg:person.010566557723.84 schema:affiliation https://www.grid.ac/institutes/grid.34428.39
    90 schema:familyName Santoro
    91 schema:givenName Nicola
    92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010566557723.84
    93 rdf:type schema:Person
    94 sg:person.011073450025.09 schema:affiliation https://www.grid.ac/institutes/grid.68312.3e
    95 schema:familyName Miri
    96 schema:givenName Ali
    97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011073450025.09
    98 rdf:type schema:Person
    99 sg:person.01127513656.68 schema:affiliation https://www.grid.ac/institutes/grid.28046.38
    100 schema:familyName Balamohan
    101 schema:givenName Balasingham
    102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01127513656.68
    103 rdf:type schema:Person
    104 sg:person.011601470625.25 schema:affiliation https://www.grid.ac/institutes/grid.28046.38
    105 schema:familyName Flocchini
    106 schema:givenName Paola
    107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011601470625.25
    108 rdf:type schema:Person
    109 sg:pub.10.1007/11758471_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031542158
    110 https://doi.org/10.1007/11758471_16
    111 rdf:type schema:CreativeWork
    112 sg:pub.10.1007/11945529_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047952182
    113 https://doi.org/10.1007/11945529_23
    114 rdf:type schema:CreativeWork
    115 sg:pub.10.1007/978-0-387-34735-6_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030142924
    116 https://doi.org/10.1007/978-0-387-34735-6_14
    117 rdf:type schema:CreativeWork
    118 sg:pub.10.1007/978-3-540-27796-5_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022687220
    119 https://doi.org/10.1007/978-3-540-27796-5_11
    120 rdf:type schema:CreativeWork
    121 sg:pub.10.1007/978-3-540-75142-7_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032317348
    122 https://doi.org/10.1007/978-3-540-75142-7_11
    123 rdf:type schema:CreativeWork
    124 sg:pub.10.1007/978-3-642-05118-0_46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016037775
    125 https://doi.org/10.1007/978-3-642-05118-0_46
    126 rdf:type schema:CreativeWork
    127 sg:pub.10.1007/978-3-642-05434-1_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017113003
    128 https://doi.org/10.1007/978-3-642-05434-1_13
    129 rdf:type schema:CreativeWork
    130 sg:pub.10.1007/978-3-642-10877-8_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031426893
    131 https://doi.org/10.1007/978-3-642-10877-8_9
    132 rdf:type schema:CreativeWork
    133 sg:pub.10.1007/978-3-642-11476-2_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033891893
    134 https://doi.org/10.1007/978-3-642-11476-2_15
    135 rdf:type schema:CreativeWork
    136 sg:pub.10.1007/978-3-642-13284-1_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023550915
    137 https://doi.org/10.1007/978-3-642-13284-1_13
    138 rdf:type schema:CreativeWork
    139 sg:pub.10.1007/978-3-642-17461-2_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033209134
    140 https://doi.org/10.1007/978-3-642-17461-2_5
    141 rdf:type schema:CreativeWork
    142 sg:pub.10.1007/s00446-006-0154-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1000916693
    143 https://doi.org/10.1007/s00446-006-0154-y
    144 rdf:type schema:CreativeWork
    145 sg:pub.10.1007/s00453-006-1232-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1027520360
    146 https://doi.org/10.1007/s00453-006-1232-z
    147 rdf:type schema:CreativeWork
    148 sg:pub.10.1007/s00453-011-9496-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033084507
    149 https://doi.org/10.1007/s00453-011-9496-3
    150 rdf:type schema:CreativeWork
    151 https://doi.org/10.1002/net.20095 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015469195
    152 rdf:type schema:CreativeWork
    153 https://doi.org/10.1002/net.20233 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028617841
    154 rdf:type schema:CreativeWork
    155 https://doi.org/10.1016/j.tcs.2007.04.024 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006130162
    156 rdf:type schema:CreativeWork
    157 https://doi.org/10.1016/j.tcs.2010.01.011 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038583630
    158 rdf:type schema:CreativeWork
    159 https://doi.org/10.1017/s0963548306008133 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045829097
    160 rdf:type schema:CreativeWork
    161 https://doi.org/10.1109/ipdps.2009.5161080 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093705627
    162 rdf:type schema:CreativeWork
    163 https://www.grid.ac/institutes/grid.28046.38 schema:alternateName University of Ottawa
    164 schema:name University of Ottawa, Ottawa, Canada
    165 rdf:type schema:Organization
    166 https://www.grid.ac/institutes/grid.34428.39 schema:alternateName Carleton University
    167 schema:name Carleton University, Ottawa, Canada
    168 rdf:type schema:Organization
    169 https://www.grid.ac/institutes/grid.68312.3e schema:alternateName Ryerson University
    170 schema:name Ryerson University, Toronto, Canada
    171 rdf:type schema:Organization
     




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


    ...