Asynchronous Exploration of an Unknown Anonymous Dangerous Graph with O(1) Pebbles View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2012

AUTHORS

Balasingham Balamohan , Stefan Dobrev , Paola Flocchini , Nicola Santoro

ABSTRACT

We consider the a team of asynchronous agents that must explore an unknown graph in presence of a black hole, a node which destroys all incoming agents without leaving any observable trace. Communication is achieved using pebbles that an agent can pick up, carry, and drop. It is known that, when the graph is unknown, Δ + 1 agents are necessary, and solutions exist with those many agents, using a total of O(logΔ) pebbles, where Δ is the max node degree. On the other hand, it is also known that if the agents have a map of the graph, the problem can be solved with O(1) pebbles in total, without increasing the size of the team. In this paper we address the question of whether it is possible to locate the black hole using O(1) pebbles even if the graph is unknown, and, if so, with how many agents. We first prove that with O(1) pebbles, Δ + 1 agents are not sufficient. We next prove that, regardless of the team size, 2 pebbles are not sufficient. We then show that these bounds are tight presenting a protocol that allows to locate a black hole in an unknown anonymous graph with only 3 pebbles and Δ + 2 agents. More... »

PAGES

279-290

References to SciGraph publications

  • 2012-01. Searching for Black Holes in Subways in THEORY OF COMPUTING SYSTEMS
  • 2011. Black Hole Search with Finite Automata Scattered in a Synchronous Torus in DISTRIBUTED COMPUTING
  • 2006. Exploring an Unknown Graph to Locate a Black Hole Using Tokens in FOURTH IFIP INTERNATIONAL CONFERENCE ON THEORETICAL COMPUTER SCIENCE- TCS 2006
  • 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
  • 2011. Improving the Optimal Bounds for Black Hole Search in Rings in STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY
  • 2009. Black Hole Search with Tokens in Interconnected Networks in STABILIZATION, SAFETY, AND SECURITY OF DISTRIBUTED SYSTEMS
  • 2010. Black Hole Search in Directed Graphs in STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY
  • 2011. Tight Bounds for Scattered Black Hole Search in a Ring 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
  • Book

    TITLE

    Structural Information and Communication Complexity

    ISBN

    978-3-642-31103-1
    978-3-642-31104-8

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-31104-8_24

    DOI

    http://dx.doi.org/10.1007/978-3-642-31104-8_24

    DIMENSIONS

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


    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/1109", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Neurosciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/11", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Medical and Health Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Ottawa", 
              "id": "https://www.grid.ac/institutes/grid.28046.38", 
              "name": [
                "EECS, 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": "Slovak Academy of Sciences", 
              "id": "https://www.grid.ac/institutes/grid.419303.c", 
              "name": [
                "Institute of Mathematics, Slovak Academy of Sciences, Bratislava, Slovak Republic"
              ], 
              "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": [
                "EECS, 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": "Carleton University", 
              "id": "https://www.grid.ac/institutes/grid.34428.39", 
              "name": [
                "School of Computer Science, 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": "sg:pub.10.1007/s00224-011-9341-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004728379", 
              "https://doi.org/10.1007/s00224-011-9341-8"
            ], 
            "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": "sg:pub.10.1007/978-3-642-22212-2_18", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014672497", 
              "https://doi.org/10.1007/978-3-642-22212-2_18"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-22212-2_18", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014672497", 
              "https://doi.org/10.1007/978-3-642-22212-2_18"
            ], 
            "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/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.1016/j.tcs.2011.05.054", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028028150"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-22212-2_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028420624", 
              "https://doi.org/10.1007/978-3-642-22212-2_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-22212-2_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028420624", 
              "https://doi.org/10.1007/978-3-642-22212-2_17"
            ], 
            "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-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-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": "sg:pub.10.1007/978-3-642-24100-0_41", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040614882", 
              "https://doi.org/10.1007/978-3-642-24100-0_41"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2012", 
        "datePublishedReg": "2012-01-01", 
        "description": "We consider the a team of asynchronous agents that must explore an unknown graph in presence of a black hole, a node which destroys all incoming agents without leaving any observable trace. Communication is achieved using pebbles that an agent can pick up, carry, and drop. It is known that, when the graph is unknown, \u0394\u2009+\u20091 agents are necessary, and solutions exist with those many agents, using a total of O(log\u0394) pebbles, where \u0394 is the max node degree. On the other hand, it is also known that if the agents have a map of the graph, the problem can be solved with O(1) pebbles in total, without increasing the size of the team. In this paper we address the question of whether it is possible to locate the black hole using O(1) pebbles even if the graph is unknown, and, if so, with how many agents. We first prove that with O(1) pebbles, \u0394\u2009+\u20091 agents are not sufficient. We next prove that, regardless of the team size, 2 pebbles are not sufficient. We then show that these bounds are tight presenting a protocol that allows to locate a black hole in an unknown anonymous graph with only 3 pebbles and \u0394\u2009+\u20092 agents.", 
        "editor": [
          {
            "familyName": "Even", 
            "givenName": "Guy", 
            "type": "Person"
          }, 
          {
            "familyName": "Halld\u00f3rsson", 
            "givenName": "Magn\u00fas M.", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-31104-8_24", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-642-31103-1", 
            "978-3-642-31104-8"
          ], 
          "name": "Structural Information and Communication Complexity", 
          "type": "Book"
        }, 
        "name": "Asynchronous Exploration of an Unknown Anonymous Dangerous Graph with O(1) Pebbles", 
        "pagination": "279-290", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-31104-8_24"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "c8477109381ad3296902b3dffdb32306f2b87278a68c425ce1bbfe8bea6bc7d3"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1042044383"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-31104-8_24", 
          "https://app.dimensions.ai/details/publication/pub.1042044383"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T18: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_8681_00000269.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-642-31104-8_24"
      }
    ]
     

    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-31104-8_24'

    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-31104-8_24'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-31104-8_24'

    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-31104-8_24'


     

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

    150 TRIPLES      23 PREDICATES      41 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-31104-8_24 schema:about anzsrc-for:11
    2 anzsrc-for:1109
    3 schema:author N3934f33b792044f48f477ff6544c41b1
    4 schema:citation sg:pub.10.1007/978-0-387-34735-6_14
    5 sg:pub.10.1007/978-3-540-75142-7_11
    6 sg:pub.10.1007/978-3-642-05118-0_46
    7 sg:pub.10.1007/978-3-642-11476-2_15
    8 sg:pub.10.1007/978-3-642-22212-2_17
    9 sg:pub.10.1007/978-3-642-22212-2_18
    10 sg:pub.10.1007/978-3-642-24100-0_41
    11 sg:pub.10.1007/s00224-011-9341-8
    12 sg:pub.10.1007/s00446-006-0154-y
    13 sg:pub.10.1007/s00453-006-1232-z
    14 sg:pub.10.1007/s00453-011-9496-3
    15 https://doi.org/10.1002/net.20233
    16 https://doi.org/10.1016/j.tcs.2007.04.024
    17 https://doi.org/10.1016/j.tcs.2011.05.054
    18 schema:datePublished 2012
    19 schema:datePublishedReg 2012-01-01
    20 schema:description We consider the a team of asynchronous agents that must explore an unknown graph in presence of a black hole, a node which destroys all incoming agents without leaving any observable trace. Communication is achieved using pebbles that an agent can pick up, carry, and drop. It is known that, when the graph is unknown, Δ + 1 agents are necessary, and solutions exist with those many agents, using a total of O(logΔ) pebbles, where Δ is the max node degree. On the other hand, it is also known that if the agents have a map of the graph, the problem can be solved with O(1) pebbles in total, without increasing the size of the team. In this paper we address the question of whether it is possible to locate the black hole using O(1) pebbles even if the graph is unknown, and, if so, with how many agents. We first prove that with O(1) pebbles, Δ + 1 agents are not sufficient. We next prove that, regardless of the team size, 2 pebbles are not sufficient. We then show that these bounds are tight presenting a protocol that allows to locate a black hole in an unknown anonymous graph with only 3 pebbles and Δ + 2 agents.
    21 schema:editor Na1e7ebd1d9a74c798e0f74ccfcfaf499
    22 schema:genre chapter
    23 schema:inLanguage en
    24 schema:isAccessibleForFree false
    25 schema:isPartOf N4e7bc616b8c841e5b391d54e0c61e695
    26 schema:name Asynchronous Exploration of an Unknown Anonymous Dangerous Graph with O(1) Pebbles
    27 schema:pagination 279-290
    28 schema:productId N48f0d3abfd5f41d1a93bc546dd6b5873
    29 N50decb36219043fd812b234152b205d2
    30 Na8c85019d305411181b19069c6ec6c26
    31 schema:publisher N136a1c5193eb40acb573e8a47c4e1b1c
    32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042044383
    33 https://doi.org/10.1007/978-3-642-31104-8_24
    34 schema:sdDatePublished 2019-04-15T18:13
    35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    36 schema:sdPublisher Nba9bb311c05549209699177d3dbd6433
    37 schema:url http://link.springer.com/10.1007/978-3-642-31104-8_24
    38 sgo:license sg:explorer/license/
    39 sgo:sdDataset chapters
    40 rdf:type schema:Chapter
    41 N136a1c5193eb40acb573e8a47c4e1b1c schema:location Berlin, Heidelberg
    42 schema:name Springer Berlin Heidelberg
    43 rdf:type schema:Organisation
    44 N3934f33b792044f48f477ff6544c41b1 rdf:first sg:person.01127513656.68
    45 rdf:rest Nd8a25c301db14ed19240c1493ca52f3a
    46 N48f0d3abfd5f41d1a93bc546dd6b5873 schema:name doi
    47 schema:value 10.1007/978-3-642-31104-8_24
    48 rdf:type schema:PropertyValue
    49 N4e7bc616b8c841e5b391d54e0c61e695 schema:isbn 978-3-642-31103-1
    50 978-3-642-31104-8
    51 schema:name Structural Information and Communication Complexity
    52 rdf:type schema:Book
    53 N50decb36219043fd812b234152b205d2 schema:name dimensions_id
    54 schema:value pub.1042044383
    55 rdf:type schema:PropertyValue
    56 N7335b2502c294bbdbb741971d009e155 rdf:first sg:person.010566557723.84
    57 rdf:rest rdf:nil
    58 N7579d1be36d1486b94960bb53584044d rdf:first sg:person.011601470625.25
    59 rdf:rest N7335b2502c294bbdbb741971d009e155
    60 N9532e6ad39f444f890831786762c3ee8 schema:familyName Halldórsson
    61 schema:givenName Magnús M.
    62 rdf:type schema:Person
    63 Na1e7ebd1d9a74c798e0f74ccfcfaf499 rdf:first Nb0568b58344b4fb4ac80ccd58ed20d42
    64 rdf:rest Ne3075136f7bf4e4386d2b4a0bc97bdf6
    65 Na8c85019d305411181b19069c6ec6c26 schema:name readcube_id
    66 schema:value c8477109381ad3296902b3dffdb32306f2b87278a68c425ce1bbfe8bea6bc7d3
    67 rdf:type schema:PropertyValue
    68 Nb0568b58344b4fb4ac80ccd58ed20d42 schema:familyName Even
    69 schema:givenName Guy
    70 rdf:type schema:Person
    71 Nba9bb311c05549209699177d3dbd6433 schema:name Springer Nature - SN SciGraph project
    72 rdf:type schema:Organization
    73 Nd8a25c301db14ed19240c1493ca52f3a rdf:first sg:person.0610371471.49
    74 rdf:rest N7579d1be36d1486b94960bb53584044d
    75 Ne3075136f7bf4e4386d2b4a0bc97bdf6 rdf:first N9532e6ad39f444f890831786762c3ee8
    76 rdf:rest rdf:nil
    77 anzsrc-for:11 schema:inDefinedTermSet anzsrc-for:
    78 schema:name Medical and Health Sciences
    79 rdf:type schema:DefinedTerm
    80 anzsrc-for:1109 schema:inDefinedTermSet anzsrc-for:
    81 schema:name Neurosciences
    82 rdf:type schema:DefinedTerm
    83 sg:person.010566557723.84 schema:affiliation https://www.grid.ac/institutes/grid.34428.39
    84 schema:familyName Santoro
    85 schema:givenName Nicola
    86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010566557723.84
    87 rdf:type schema:Person
    88 sg:person.01127513656.68 schema:affiliation https://www.grid.ac/institutes/grid.28046.38
    89 schema:familyName Balamohan
    90 schema:givenName Balasingham
    91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01127513656.68
    92 rdf:type schema:Person
    93 sg:person.011601470625.25 schema:affiliation https://www.grid.ac/institutes/grid.28046.38
    94 schema:familyName Flocchini
    95 schema:givenName Paola
    96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011601470625.25
    97 rdf:type schema:Person
    98 sg:person.0610371471.49 schema:affiliation https://www.grid.ac/institutes/grid.419303.c
    99 schema:familyName Dobrev
    100 schema:givenName Stefan
    101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0610371471.49
    102 rdf:type schema:Person
    103 sg:pub.10.1007/978-0-387-34735-6_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030142924
    104 https://doi.org/10.1007/978-0-387-34735-6_14
    105 rdf:type schema:CreativeWork
    106 sg:pub.10.1007/978-3-540-75142-7_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032317348
    107 https://doi.org/10.1007/978-3-540-75142-7_11
    108 rdf:type schema:CreativeWork
    109 sg:pub.10.1007/978-3-642-05118-0_46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016037775
    110 https://doi.org/10.1007/978-3-642-05118-0_46
    111 rdf:type schema:CreativeWork
    112 sg:pub.10.1007/978-3-642-11476-2_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033891893
    113 https://doi.org/10.1007/978-3-642-11476-2_15
    114 rdf:type schema:CreativeWork
    115 sg:pub.10.1007/978-3-642-22212-2_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028420624
    116 https://doi.org/10.1007/978-3-642-22212-2_17
    117 rdf:type schema:CreativeWork
    118 sg:pub.10.1007/978-3-642-22212-2_18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014672497
    119 https://doi.org/10.1007/978-3-642-22212-2_18
    120 rdf:type schema:CreativeWork
    121 sg:pub.10.1007/978-3-642-24100-0_41 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040614882
    122 https://doi.org/10.1007/978-3-642-24100-0_41
    123 rdf:type schema:CreativeWork
    124 sg:pub.10.1007/s00224-011-9341-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004728379
    125 https://doi.org/10.1007/s00224-011-9341-8
    126 rdf:type schema:CreativeWork
    127 sg:pub.10.1007/s00446-006-0154-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1000916693
    128 https://doi.org/10.1007/s00446-006-0154-y
    129 rdf:type schema:CreativeWork
    130 sg:pub.10.1007/s00453-006-1232-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1027520360
    131 https://doi.org/10.1007/s00453-006-1232-z
    132 rdf:type schema:CreativeWork
    133 sg:pub.10.1007/s00453-011-9496-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033084507
    134 https://doi.org/10.1007/s00453-011-9496-3
    135 rdf:type schema:CreativeWork
    136 https://doi.org/10.1002/net.20233 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028617841
    137 rdf:type schema:CreativeWork
    138 https://doi.org/10.1016/j.tcs.2007.04.024 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006130162
    139 rdf:type schema:CreativeWork
    140 https://doi.org/10.1016/j.tcs.2011.05.054 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028028150
    141 rdf:type schema:CreativeWork
    142 https://www.grid.ac/institutes/grid.28046.38 schema:alternateName University of Ottawa
    143 schema:name EECS, University of Ottawa, Ottawa, Canada
    144 rdf:type schema:Organization
    145 https://www.grid.ac/institutes/grid.34428.39 schema:alternateName Carleton University
    146 schema:name School of Computer Science, Carleton University, Ottawa, Canada
    147 rdf:type schema:Organization
    148 https://www.grid.ac/institutes/grid.419303.c schema:alternateName Slovak Academy of Sciences
    149 schema:name Institute of Mathematics, Slovak Academy of Sciences, Bratislava, Slovak Republic
    150 rdf:type schema:Organization
     




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


    ...