Black Hole Search in Directed Graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2010

AUTHORS

Jurek Czyzowicz , Stefan Dobrev , Rastislav Královič , Stanislav Miklík , Dana Pardubská

ABSTRACT

We consider the problem of cooperative network exploration by agents under the assumption that there is a harmful host present in the network that destroys the incoming agents without outside trace – the so-called black hole search problem. Many variants of this problem have been studied, with various assumptions about the timing, agents’ knowledge about the topology, means of inter-agent communication, amount of writable memory in vertices, and other parameters. However, all this research considered undirected graphs only, and relied to some extent on the ability of an agent to mark an edge as safe immediately after having traversed it. In this paper we study directed graphs where this technique does not apply, and show that the consequence is an exponential gap: While in undirected graphs Δ + 1 agents are always sufficient, in the directed case at least 2Δ agents are needed in the worst case, where Δ is in-degree of the black hole. This lower bound holds also in the case of synchronous agents. Furthermore, we ask the question What structural information is sufficient to close this gap? and show that in planar graphs with a planar embedding known to the agents, 2Δ + 1 agents are sufficient, and 2Δ agents are necessary. More... »

PAGES

182-194

References to SciGraph publications

  • 2005. Hardness and Approximation Results for Black Hole Search in Arbitrary Graphs in STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY
  • 2005. Asynchronous Deterministic Rendezvous in Graphs in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2005
  • 2003. Host Revocation Authority: A Way of Protecting Mobile Agents from Malicious Hosts in WEB ENGINEERING
  • 2004. Digraphs Exploration with Little Memory in STACS 2004
  • 1981. One pebble does not suffice to search plane labyrinths in FUNDAMENTALS OF COMPUTATION THEORY
  • 2007-05. Mobile Search for a Black Hole in an Anonymous Ring in ALGORITHMICA
  • 2004. Multiple Agents RendezVous in a Ring in Spite of a Black Hole in PRINCIPLES OF DISTRIBUTED SYSTEMS
  • 2005. Searching for a Black Hole in Tree Networks in PRINCIPLES OF DISTRIBUTED SYSTEMS
  • 1998. Protecting Mobile Agents Against Malicious Hosts in MOBILE AGENTS AND SECURITY
  • 2004. Improved Bounds for Optimal Black Hole Search with a Network Map in STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY
  • Book

    TITLE

    Structural Information and Communication Complexity

    ISBN

    978-3-642-11475-5
    978-3-642-11476-2

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-11476-2_15

    DOI

    http://dx.doi.org/10.1007/978-3-642-11476-2_15

    DIMENSIONS

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


    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": "Universit\u00e9 du Qu\u00e9bec en Outaouais", 
              "id": "https://www.grid.ac/institutes/grid.265705.3", 
              "name": [
                "Universit\u00e9 du Qu\u00e9bec en Outaouais, Gatineau, Qu\u00e9bec, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Czyzowicz", 
            "givenName": "Jurek", 
            "id": "sg:person.011042601565.30", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011042601565.30"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Slovak Academy of Sciences", 
              "id": "https://www.grid.ac/institutes/grid.419303.c", 
              "name": [
                "Slovak Academy of Sciences, Bratislava, Slovakia"
              ], 
              "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": "Comenius University", 
              "id": "https://www.grid.ac/institutes/grid.7634.6", 
              "name": [
                "Comenius University, Bratislava, Slovakia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kr\u00e1lovi\u010d", 
            "givenName": "Rastislav", 
            "id": "sg:person.016260121541.79", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016260121541.79"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Comenius University", 
              "id": "https://www.grid.ac/institutes/grid.7634.6", 
              "name": [
                "Comenius University, Bratislava, Slovakia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Mikl\u00edk", 
            "givenName": "Stanislav", 
            "id": "sg:person.014014770442.71", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014014770442.71"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Comenius University", 
              "id": "https://www.grid.ac/institutes/grid.7634.6", 
              "name": [
                "Comenius University, Bratislava, Slovakia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Pardubsk\u00e1", 
            "givenName": "Dana", 
            "id": "sg:person.011643142735.67", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011643142735.67"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-540-27860-3_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006100921", 
              "https://doi.org/10.1007/978-3-540-27860-3_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-27860-3_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006100921", 
              "https://doi.org/10.1007/978-3-540-27860-3_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2005.07.014", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006352716"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2005.07.014", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006352716"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0004-3702(99)00107-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007552506"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11516798_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008634147", 
              "https://doi.org/10.1007/11516798_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11516798_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008634147", 
              "https://doi.org/10.1007/11516798_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jagm.1999.1043", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014281330"
            ], 
            "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-540-24749-4_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019111927", 
              "https://doi.org/10.1007/978-3-540-24749-4_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-24749-4_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019111927", 
              "https://doi.org/10.1007/978-3-540-24749-4_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/276698.276759", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022410991"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-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/11549345_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022874040", 
              "https://doi.org/10.1007/11549345_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11549345_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022874040", 
              "https://doi.org/10.1007/11549345_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11549345_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022874040", 
              "https://doi.org/10.1007/11549345_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-68671-1_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024187435", 
              "https://doi.org/10.1007/3-540-68671-1_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.dam.2007.11.001", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025351675"
            ], 
            "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/s0140-3664(99)00083-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028258284"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1383369.1383373", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028971713"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-10854-8_47", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030264159", 
              "https://doi.org/10.1007/3-540-10854-8_47"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.ic.2008.07.005", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036666426"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45068-8_54", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037532085", 
              "https://doi.org/10.1007/3-540-45068-8_54"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11429647_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045504329", 
              "https://doi.org/10.1007/11429647_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11429647_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045504329", 
              "https://doi.org/10.1007/11429647_17"
            ], 
            "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.1002/net.20127", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053686921"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/35.689634", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061159636"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/fscs.1990.89554", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086329143"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1994.365703", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093260501"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2010", 
        "datePublishedReg": "2010-01-01", 
        "description": "We consider the problem of cooperative network exploration by agents under the assumption that there is a harmful host present in the network that destroys the incoming agents without outside trace \u2013 the so-called black hole search problem. Many variants of this problem have been studied, with various assumptions about the timing, agents\u2019 knowledge about the topology, means of inter-agent communication, amount of writable memory in vertices, and other parameters. However, all this research considered undirected graphs only, and relied to some extent on the ability of an agent to mark an edge as safe immediately after having traversed it. In this paper we study directed graphs where this technique does not apply, and show that the consequence is an exponential gap: While in undirected graphs \u0394 + 1 agents are always sufficient, in the directed case at least 2\u0394 agents are needed in the worst case, where \u0394 is in-degree of the black hole. This lower bound holds also in the case of synchronous agents. Furthermore, we ask the question What structural information is sufficient to close this gap? and show that in planar graphs with a planar embedding known to the agents, 2\u0394 + 1 agents are sufficient, and 2\u0394 agents are necessary.", 
        "editor": [
          {
            "familyName": "Kutten", 
            "givenName": "Shay", 
            "type": "Person"
          }, 
          {
            "familyName": "\u017derovnik", 
            "givenName": "Janez", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-11476-2_15", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-642-11475-5", 
            "978-3-642-11476-2"
          ], 
          "name": "Structural Information and Communication Complexity", 
          "type": "Book"
        }, 
        "name": "Black Hole Search in Directed Graphs", 
        "pagination": "182-194", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1033891893"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-11476-2_15"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "a173c7837d1226d2122deda6490c64f54261c78d3462756bb2109bb3d9ab0ded"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-11476-2_15", 
          "https://app.dimensions.ai/details/publication/pub.1033891893"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T07:29", 
        "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/0000000356_0000000356/records_57865_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-642-11476-2_15"
      }
    ]
     

    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-11476-2_15'

    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-11476-2_15'

    Turtle is a human-readable linked data format.

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

    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-11476-2_15'


     

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

    186 TRIPLES      23 PREDICATES      51 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-11476-2_15 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Nf4f381dfd9154b259ad6025e3828fedc
    4 schema:citation sg:pub.10.1007/11429647_17
    5 sg:pub.10.1007/11516798_5
    6 sg:pub.10.1007/11549345_24
    7 sg:pub.10.1007/3-540-10854-8_47
    8 sg:pub.10.1007/3-540-45068-8_54
    9 sg:pub.10.1007/3-540-68671-1_4
    10 sg:pub.10.1007/978-3-540-24749-4_22
    11 sg:pub.10.1007/978-3-540-27796-5_11
    12 sg:pub.10.1007/978-3-540-27860-3_6
    13 sg:pub.10.1007/s00453-006-1232-z
    14 https://doi.org/10.1002/net.20095
    15 https://doi.org/10.1002/net.20127
    16 https://doi.org/10.1006/jagm.1999.1043
    17 https://doi.org/10.1016/j.dam.2007.11.001
    18 https://doi.org/10.1016/j.ic.2008.07.005
    19 https://doi.org/10.1016/j.tcs.2005.07.014
    20 https://doi.org/10.1016/s0004-3702(99)00107-1
    21 https://doi.org/10.1016/s0140-3664(99)00083-3
    22 https://doi.org/10.1109/35.689634
    23 https://doi.org/10.1109/fscs.1990.89554
    24 https://doi.org/10.1109/sfcs.1994.365703
    25 https://doi.org/10.1145/1383369.1383373
    26 https://doi.org/10.1145/276698.276759
    27 https://doi.org/10.1145/564870.564906
    28 schema:datePublished 2010
    29 schema:datePublishedReg 2010-01-01
    30 schema:description We consider the problem of cooperative network exploration by agents under the assumption that there is a harmful host present in the network that destroys the incoming agents without outside trace – the so-called black hole search problem. Many variants of this problem have been studied, with various assumptions about the timing, agents’ knowledge about the topology, means of inter-agent communication, amount of writable memory in vertices, and other parameters. However, all this research considered undirected graphs only, and relied to some extent on the ability of an agent to mark an edge as safe immediately after having traversed it. In this paper we study directed graphs where this technique does not apply, and show that the consequence is an exponential gap: While in undirected graphs Δ + 1 agents are always sufficient, in the directed case at least 2Δ agents are needed in the worst case, where Δ is in-degree of the black hole. This lower bound holds also in the case of synchronous agents. Furthermore, we ask the question What structural information is sufficient to close this gap? and show that in planar graphs with a planar embedding known to the agents, 2Δ + 1 agents are sufficient, and 2Δ agents are necessary.
    31 schema:editor Nc2e49065e74946c489afd453b4a27cbf
    32 schema:genre chapter
    33 schema:inLanguage en
    34 schema:isAccessibleForFree false
    35 schema:isPartOf N1482121e23074e66be1ea236674e21c4
    36 schema:name Black Hole Search in Directed Graphs
    37 schema:pagination 182-194
    38 schema:productId N38ea5030ab5249719c9c601358ace144
    39 N729f5a36289d4fbb9bc3eb100b04a278
    40 Nf877302fa1b94319af00fff3ee42a2ac
    41 schema:publisher N88ab341bc81e41ada260e2685d885002
    42 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033891893
    43 https://doi.org/10.1007/978-3-642-11476-2_15
    44 schema:sdDatePublished 2019-04-16T07:29
    45 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    46 schema:sdPublisher Nfcbd20230b654b7a978f3832b2f96d13
    47 schema:url https://link.springer.com/10.1007%2F978-3-642-11476-2_15
    48 sgo:license sg:explorer/license/
    49 sgo:sdDataset chapters
    50 rdf:type schema:Chapter
    51 N1482121e23074e66be1ea236674e21c4 schema:isbn 978-3-642-11475-5
    52 978-3-642-11476-2
    53 schema:name Structural Information and Communication Complexity
    54 rdf:type schema:Book
    55 N1b2611252ef445968555f6d85144c649 rdf:first sg:person.0610371471.49
    56 rdf:rest Nc42b305ab06f4d53aae672560d1bd655
    57 N351d757c158347d98d753a4abf5cc961 schema:familyName Kutten
    58 schema:givenName Shay
    59 rdf:type schema:Person
    60 N38ea5030ab5249719c9c601358ace144 schema:name readcube_id
    61 schema:value a173c7837d1226d2122deda6490c64f54261c78d3462756bb2109bb3d9ab0ded
    62 rdf:type schema:PropertyValue
    63 N3b038030f23f425d94420a74fa7c0274 rdf:first Nfee48f0b8cbe4ecc80a54f91dce339ff
    64 rdf:rest rdf:nil
    65 N4d65fb20093d43a5814fec5cef52e452 rdf:first sg:person.014014770442.71
    66 rdf:rest N6777065864e6419fb8f1534941a598ef
    67 N6777065864e6419fb8f1534941a598ef rdf:first sg:person.011643142735.67
    68 rdf:rest rdf:nil
    69 N729f5a36289d4fbb9bc3eb100b04a278 schema:name doi
    70 schema:value 10.1007/978-3-642-11476-2_15
    71 rdf:type schema:PropertyValue
    72 N88ab341bc81e41ada260e2685d885002 schema:location Berlin, Heidelberg
    73 schema:name Springer Berlin Heidelberg
    74 rdf:type schema:Organisation
    75 Nc2e49065e74946c489afd453b4a27cbf rdf:first N351d757c158347d98d753a4abf5cc961
    76 rdf:rest N3b038030f23f425d94420a74fa7c0274
    77 Nc42b305ab06f4d53aae672560d1bd655 rdf:first sg:person.016260121541.79
    78 rdf:rest N4d65fb20093d43a5814fec5cef52e452
    79 Nf4f381dfd9154b259ad6025e3828fedc rdf:first sg:person.011042601565.30
    80 rdf:rest N1b2611252ef445968555f6d85144c649
    81 Nf877302fa1b94319af00fff3ee42a2ac schema:name dimensions_id
    82 schema:value pub.1033891893
    83 rdf:type schema:PropertyValue
    84 Nfcbd20230b654b7a978f3832b2f96d13 schema:name Springer Nature - SN SciGraph project
    85 rdf:type schema:Organization
    86 Nfee48f0b8cbe4ecc80a54f91dce339ff schema:familyName Žerovnik
    87 schema:givenName Janez
    88 rdf:type schema:Person
    89 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    90 schema:name Information and Computing Sciences
    91 rdf:type schema:DefinedTerm
    92 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    93 schema:name Computation Theory and Mathematics
    94 rdf:type schema:DefinedTerm
    95 sg:person.011042601565.30 schema:affiliation https://www.grid.ac/institutes/grid.265705.3
    96 schema:familyName Czyzowicz
    97 schema:givenName Jurek
    98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011042601565.30
    99 rdf:type schema:Person
    100 sg:person.011643142735.67 schema:affiliation https://www.grid.ac/institutes/grid.7634.6
    101 schema:familyName Pardubská
    102 schema:givenName Dana
    103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011643142735.67
    104 rdf:type schema:Person
    105 sg:person.014014770442.71 schema:affiliation https://www.grid.ac/institutes/grid.7634.6
    106 schema:familyName Miklík
    107 schema:givenName Stanislav
    108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014014770442.71
    109 rdf:type schema:Person
    110 sg:person.016260121541.79 schema:affiliation https://www.grid.ac/institutes/grid.7634.6
    111 schema:familyName Královič
    112 schema:givenName Rastislav
    113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016260121541.79
    114 rdf:type schema:Person
    115 sg:person.0610371471.49 schema:affiliation https://www.grid.ac/institutes/grid.419303.c
    116 schema:familyName Dobrev
    117 schema:givenName Stefan
    118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0610371471.49
    119 rdf:type schema:Person
    120 sg:pub.10.1007/11429647_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045504329
    121 https://doi.org/10.1007/11429647_17
    122 rdf:type schema:CreativeWork
    123 sg:pub.10.1007/11516798_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008634147
    124 https://doi.org/10.1007/11516798_5
    125 rdf:type schema:CreativeWork
    126 sg:pub.10.1007/11549345_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022874040
    127 https://doi.org/10.1007/11549345_24
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/3-540-10854-8_47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030264159
    130 https://doi.org/10.1007/3-540-10854-8_47
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1007/3-540-45068-8_54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037532085
    133 https://doi.org/10.1007/3-540-45068-8_54
    134 rdf:type schema:CreativeWork
    135 sg:pub.10.1007/3-540-68671-1_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024187435
    136 https://doi.org/10.1007/3-540-68671-1_4
    137 rdf:type schema:CreativeWork
    138 sg:pub.10.1007/978-3-540-24749-4_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019111927
    139 https://doi.org/10.1007/978-3-540-24749-4_22
    140 rdf:type schema:CreativeWork
    141 sg:pub.10.1007/978-3-540-27796-5_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022687220
    142 https://doi.org/10.1007/978-3-540-27796-5_11
    143 rdf:type schema:CreativeWork
    144 sg:pub.10.1007/978-3-540-27860-3_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006100921
    145 https://doi.org/10.1007/978-3-540-27860-3_6
    146 rdf:type schema:CreativeWork
    147 sg:pub.10.1007/s00453-006-1232-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1027520360
    148 https://doi.org/10.1007/s00453-006-1232-z
    149 rdf:type schema:CreativeWork
    150 https://doi.org/10.1002/net.20095 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015469195
    151 rdf:type schema:CreativeWork
    152 https://doi.org/10.1002/net.20127 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053686921
    153 rdf:type schema:CreativeWork
    154 https://doi.org/10.1006/jagm.1999.1043 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014281330
    155 rdf:type schema:CreativeWork
    156 https://doi.org/10.1016/j.dam.2007.11.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025351675
    157 rdf:type schema:CreativeWork
    158 https://doi.org/10.1016/j.ic.2008.07.005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036666426
    159 rdf:type schema:CreativeWork
    160 https://doi.org/10.1016/j.tcs.2005.07.014 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006352716
    161 rdf:type schema:CreativeWork
    162 https://doi.org/10.1016/s0004-3702(99)00107-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007552506
    163 rdf:type schema:CreativeWork
    164 https://doi.org/10.1016/s0140-3664(99)00083-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028258284
    165 rdf:type schema:CreativeWork
    166 https://doi.org/10.1109/35.689634 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061159636
    167 rdf:type schema:CreativeWork
    168 https://doi.org/10.1109/fscs.1990.89554 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086329143
    169 rdf:type schema:CreativeWork
    170 https://doi.org/10.1109/sfcs.1994.365703 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093260501
    171 rdf:type schema:CreativeWork
    172 https://doi.org/10.1145/1383369.1383373 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028971713
    173 rdf:type schema:CreativeWork
    174 https://doi.org/10.1145/276698.276759 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022410991
    175 rdf:type schema:CreativeWork
    176 https://doi.org/10.1145/564870.564906 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051619886
    177 rdf:type schema:CreativeWork
    178 https://www.grid.ac/institutes/grid.265705.3 schema:alternateName Université du Québec en Outaouais
    179 schema:name Université du Québec en Outaouais, Gatineau, Québec, Canada
    180 rdf:type schema:Organization
    181 https://www.grid.ac/institutes/grid.419303.c schema:alternateName Slovak Academy of Sciences
    182 schema:name Slovak Academy of Sciences, Bratislava, Slovakia
    183 rdf:type schema:Organization
    184 https://www.grid.ac/institutes/grid.7634.6 schema:alternateName Comenius University
    185 schema:name Comenius University, Bratislava, Slovakia
    186 rdf:type schema:Organization
     




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


    ...