Rumor Spreading in Random Evolving Graphs View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2013

AUTHORS

Andrea Clementi , Pierluigi Crescenzi , Carola Doerr , Pierre Fraigniaud , Marco Isopi , Alessandro Panconesi , Francesco Pasquale , Riccardo Silvestri

ABSTRACT

In this paper, we aim at analyzing the classical information spreading push protocol in dynamic networks. We consider the edge-Markovian evolving graph model which captures natural temporal dependencies between the structure of the network at time t, and the one at time t + 1. Precisely, a non-edge appears with probability p, while an existing edge dies with probability q. In order to fit with real-world traces, we mostly concentrate our study on the case where \(p=\Omega(\frac{1}{n})\) and q is constant. We prove that, in this realistic scenario, the push protocol does perform well, completing information spreading in O(logn) time steps, w.h.p., even when the network is, w.h.p., disconnected at every time step (e.g., when \(p\ll \frac{\log n}{n}\)). The bound is tight. We also address other ranges of parameters p and q (e.g., p + q = 1 with arbitrary p and q, and \(p=\Theta\left(\frac{1}{n}\right)\) with arbitrary q). Although they do not precisely fit with the measures performed on real-world traces, they can be of independent interest for other settings. The results in these cases confirm the positive impact of dynamism. More... »

PAGES

325-336

References to SciGraph publications

  • 2009. Rumor Spreading in Social Networks in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2008. How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs) in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2011-09. Parsimonious flooding in dynamic graphs in DISTRIBUTED COMPUTING
  • Book

    TITLE

    Algorithms – ESA 2013

    ISBN

    978-3-642-40449-8
    978-3-642-40450-4

    From Grant

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-40450-4_28

    DOI

    http://dx.doi.org/10.1007/978-3-642-40450-4_28

    DIMENSIONS

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


    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/0806", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information Systems", 
            "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 Rome Tor Vergata", 
              "id": "https://www.grid.ac/institutes/grid.6530.0", 
              "name": [
                "Universit\u00e0 Tor Vergata di Roma, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Clementi", 
            "givenName": "Andrea", 
            "id": "sg:person.011027660123.21", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011027660123.21"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Florence", 
              "id": "https://www.grid.ac/institutes/grid.8404.8", 
              "name": [
                "Universit\u00e0 di Firenze, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Crescenzi", 
            "givenName": "Pierluigi", 
            "id": "sg:person.01173734710.11", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01173734710.11"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "Universit\u00e9 Paris Diderot and Max Planck Institute Saarbr\u00fccken, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Doerr", 
            "givenName": "Carola", 
            "id": "sg:person.010360414373.45", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010360414373.45"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Paris Diderot University", 
              "id": "https://www.grid.ac/institutes/grid.7452.4", 
              "name": [
                "CNRS and Universit\u00e9 Paris Diderot, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Fraigniaud", 
            "givenName": "Pierre", 
            "id": "sg:person.013424402135.28", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013424402135.28"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Sapienza Universit\u00e0 di Roma, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Isopi", 
            "givenName": "Marco", 
            "id": "sg:person.01074702127.76", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01074702127.76"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Sapienza Universit\u00e0 di Roma, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Panconesi", 
            "givenName": "Alessandro", 
            "id": "sg:person.012766154071.70", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012766154071.70"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Sapienza Universit\u00e0 di Roma, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Pasquale", 
            "givenName": "Francesco", 
            "id": "sg:person.010366026047.55", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010366026047.55"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Sapienza Universit\u00e0 di Roma, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Silvestri", 
            "givenName": "Riccardo", 
            "id": "sg:person.012430640403.64", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012430640403.64"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/0166-218x(85)90059-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006274177"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0166-218x(85)90059-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006274177"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jcss.2008.10.004", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012670906"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-02930-1_31", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015749499", 
              "https://doi.org/10.1007/978-3-642-02930-1_31"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-02930-1_31", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015749499", 
              "https://doi.org/10.1007/978-3-642-02930-1_31"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1275517.1275520", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020884413"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.dam.2012.10.014", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021452341"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/41840.41841", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022752417"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1317379.1317381", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024688335"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-70575-8_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027002019", 
              "https://doi.org/10.1007/978-3-540-70575-8_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00446-011-0133-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031581381", 
              "https://doi.org/10.1007/s00446-011-0133-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1098/rspa.2009.0456", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034339761"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/rsa.3240010406", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041604066"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1959045.1959064", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043459609"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/301308.301362", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043953521"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1806689.1806760", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046808496"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tcomm.2011.020811.090163", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061558027"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tit.2010.2059830", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061652914"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tpds.2011.33", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061753875"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0147013", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062840489"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/090756053", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062856216"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0097539795288490", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062880047"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1214/aoms/1177706098", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064400899"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1.9781611973075.135", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1088801192"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1.9781611973082.37", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1088801356"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1.9781611973099.129", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1088801412"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1.9781611973099.130", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1088801465"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.2000.892324", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093211058"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/infcom.2010.5462084", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093991060"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/infcom.2005.1498447", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094179603"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/infcom.2011.5935249", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095207416"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2013", 
        "datePublishedReg": "2013-01-01", 
        "description": "In this paper, we aim at analyzing the classical information spreading push protocol in dynamic networks. We consider the edge-Markovian evolving graph model which captures natural temporal dependencies between the structure of the network at time t, and the one at time t\u2009+\u20091. Precisely, a non-edge appears with probability p, while an existing edge dies with probability q. In order to fit with real-world traces, we mostly concentrate our study on the case where \\(p=\\Omega(\\frac{1}{n})\\) and q is constant. We prove that, in this realistic scenario, the push protocol does perform well, completing information spreading in O(logn) time steps, w.h.p., even when the network is, w.h.p., disconnected at every time step (e.g., when \\(p\\ll \\frac{\\log n}{n}\\)). The bound is tight. We also address other ranges of parameters p and q (e.g., p\u2009+\u2009q\u2009=\u20091 with arbitrary p and q, and \\(p=\\Theta\\left(\\frac{1}{n}\\right)\\) with arbitrary q). Although they do not precisely fit with the measures performed on real-world traces, they can be of independent interest for other settings. The results in these cases confirm the positive impact of dynamism.", 
        "editor": [
          {
            "familyName": "Bodlaender", 
            "givenName": "Hans L.", 
            "type": "Person"
          }, 
          {
            "familyName": "Italiano", 
            "givenName": "Giuseppe F.", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-40450-4_28", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.3791124", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": {
          "isbn": [
            "978-3-642-40449-8", 
            "978-3-642-40450-4"
          ], 
          "name": "Algorithms \u2013 ESA 2013", 
          "type": "Book"
        }, 
        "name": "Rumor Spreading in Random Evolving Graphs", 
        "pagination": "325-336", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-40450-4_28"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "58773dc08137b8776996f73307759e1a5b12001fd98c42a366833b6f414d4879"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1018567336"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-40450-4_28", 
          "https://app.dimensions.ai/details/publication/pub.1018567336"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T10:33", 
        "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_8659_00000254.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-642-40450-4_28"
      }
    ]
     

    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-40450-4_28'

    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-40450-4_28'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-40450-4_28'

    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-40450-4_28'


     

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

    222 TRIPLES      23 PREDICATES      56 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-40450-4_28 schema:about anzsrc-for:08
    2 anzsrc-for:0806
    3 schema:author N79b1d0a3148046f8be33f4939088b350
    4 schema:citation sg:pub.10.1007/978-3-540-70575-8_11
    5 sg:pub.10.1007/978-3-642-02930-1_31
    6 sg:pub.10.1007/s00446-011-0133-9
    7 https://doi.org/10.1002/rsa.3240010406
    8 https://doi.org/10.1016/0166-218x(85)90059-9
    9 https://doi.org/10.1016/j.dam.2012.10.014
    10 https://doi.org/10.1016/j.jcss.2008.10.004
    11 https://doi.org/10.1098/rspa.2009.0456
    12 https://doi.org/10.1109/infcom.2005.1498447
    13 https://doi.org/10.1109/infcom.2010.5462084
    14 https://doi.org/10.1109/infcom.2011.5935249
    15 https://doi.org/10.1109/sfcs.2000.892324
    16 https://doi.org/10.1109/tcomm.2011.020811.090163
    17 https://doi.org/10.1109/tit.2010.2059830
    18 https://doi.org/10.1109/tpds.2011.33
    19 https://doi.org/10.1137/0147013
    20 https://doi.org/10.1137/090756053
    21 https://doi.org/10.1137/1.9781611973075.135
    22 https://doi.org/10.1137/1.9781611973082.37
    23 https://doi.org/10.1137/1.9781611973099.129
    24 https://doi.org/10.1137/1.9781611973099.130
    25 https://doi.org/10.1137/s0097539795288490
    26 https://doi.org/10.1145/1275517.1275520
    27 https://doi.org/10.1145/1317379.1317381
    28 https://doi.org/10.1145/1806689.1806760
    29 https://doi.org/10.1145/1959045.1959064
    30 https://doi.org/10.1145/301308.301362
    31 https://doi.org/10.1145/41840.41841
    32 https://doi.org/10.1214/aoms/1177706098
    33 schema:datePublished 2013
    34 schema:datePublishedReg 2013-01-01
    35 schema:description In this paper, we aim at analyzing the classical information spreading push protocol in dynamic networks. We consider the edge-Markovian evolving graph model which captures natural temporal dependencies between the structure of the network at time t, and the one at time t + 1. Precisely, a non-edge appears with probability p, while an existing edge dies with probability q. In order to fit with real-world traces, we mostly concentrate our study on the case where \(p=\Omega(\frac{1}{n})\) and q is constant. We prove that, in this realistic scenario, the push protocol does perform well, completing information spreading in O(logn) time steps, w.h.p., even when the network is, w.h.p., disconnected at every time step (e.g., when \(p\ll \frac{\log n}{n}\)). The bound is tight. We also address other ranges of parameters p and q (e.g., p + q = 1 with arbitrary p and q, and \(p=\Theta\left(\frac{1}{n}\right)\) with arbitrary q). Although they do not precisely fit with the measures performed on real-world traces, they can be of independent interest for other settings. The results in these cases confirm the positive impact of dynamism.
    36 schema:editor N8e01b9e89884470fb43879797b12eef9
    37 schema:genre chapter
    38 schema:inLanguage en
    39 schema:isAccessibleForFree true
    40 schema:isPartOf Nb3ad63c2750143b982b6a55fe6f708fc
    41 schema:name Rumor Spreading in Random Evolving Graphs
    42 schema:pagination 325-336
    43 schema:productId N85648f1f1ebc44b6bd33ce76309434fe
    44 Nb4a0c0e0f8964d2680ee0d42f9e94879
    45 Ne03fc78e32a243c59d1290534a984a26
    46 schema:publisher N0b4329099d704941a0f640a973a42974
    47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018567336
    48 https://doi.org/10.1007/978-3-642-40450-4_28
    49 schema:sdDatePublished 2019-04-15T10:33
    50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    51 schema:sdPublisher Nbd8191905c734da29565e49b61597043
    52 schema:url http://link.springer.com/10.1007/978-3-642-40450-4_28
    53 sgo:license sg:explorer/license/
    54 sgo:sdDataset chapters
    55 rdf:type schema:Chapter
    56 N0b4329099d704941a0f640a973a42974 schema:location Berlin, Heidelberg
    57 schema:name Springer Berlin Heidelberg
    58 rdf:type schema:Organisation
    59 N23681e9016dd45b597358dcfed778e25 rdf:first sg:person.01173734710.11
    60 rdf:rest Nbca0bbb56a23480d867328bfdb1be432
    61 N294305ea8b6241aead8d1c8375982ae1 rdf:first Ncd59cc26ae35429ba0c66744a5760cf4
    62 rdf:rest rdf:nil
    63 N3aaaed6b71d34f44b9f0f189f63dd9c2 rdf:first sg:person.010366026047.55
    64 rdf:rest Nf3e808b520a84fc9a816186361bb17b1
    65 N475aa54d002b4ffda493325ddac5f32f rdf:first sg:person.013424402135.28
    66 rdf:rest Nf45af8589d0b4e07b489b93ad72da0cd
    67 N79b1d0a3148046f8be33f4939088b350 rdf:first sg:person.011027660123.21
    68 rdf:rest N23681e9016dd45b597358dcfed778e25
    69 N85648f1f1ebc44b6bd33ce76309434fe schema:name doi
    70 schema:value 10.1007/978-3-642-40450-4_28
    71 rdf:type schema:PropertyValue
    72 N8e01b9e89884470fb43879797b12eef9 rdf:first Ne48067da2c124d8e87a20c9c79a42389
    73 rdf:rest N294305ea8b6241aead8d1c8375982ae1
    74 N951241d4dfea43c0b7b53869bff1bef7 rdf:first sg:person.012766154071.70
    75 rdf:rest N3aaaed6b71d34f44b9f0f189f63dd9c2
    76 Nb3ad63c2750143b982b6a55fe6f708fc schema:isbn 978-3-642-40449-8
    77 978-3-642-40450-4
    78 schema:name Algorithms – ESA 2013
    79 rdf:type schema:Book
    80 Nb4a0c0e0f8964d2680ee0d42f9e94879 schema:name readcube_id
    81 schema:value 58773dc08137b8776996f73307759e1a5b12001fd98c42a366833b6f414d4879
    82 rdf:type schema:PropertyValue
    83 Nbca0bbb56a23480d867328bfdb1be432 rdf:first sg:person.010360414373.45
    84 rdf:rest N475aa54d002b4ffda493325ddac5f32f
    85 Nbd8191905c734da29565e49b61597043 schema:name Springer Nature - SN SciGraph project
    86 rdf:type schema:Organization
    87 Ncd59cc26ae35429ba0c66744a5760cf4 schema:familyName Italiano
    88 schema:givenName Giuseppe F.
    89 rdf:type schema:Person
    90 Ndbdb208ca9d74f5d8348cce1de91088b schema:name Université Paris Diderot and Max Planck Institute Saarbrücken, Germany
    91 rdf:type schema:Organization
    92 Ne03fc78e32a243c59d1290534a984a26 schema:name dimensions_id
    93 schema:value pub.1018567336
    94 rdf:type schema:PropertyValue
    95 Ne48067da2c124d8e87a20c9c79a42389 schema:familyName Bodlaender
    96 schema:givenName Hans L.
    97 rdf:type schema:Person
    98 Nf3e808b520a84fc9a816186361bb17b1 rdf:first sg:person.012430640403.64
    99 rdf:rest rdf:nil
    100 Nf45af8589d0b4e07b489b93ad72da0cd rdf:first sg:person.01074702127.76
    101 rdf:rest N951241d4dfea43c0b7b53869bff1bef7
    102 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    103 schema:name Information and Computing Sciences
    104 rdf:type schema:DefinedTerm
    105 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
    106 schema:name Information Systems
    107 rdf:type schema:DefinedTerm
    108 sg:grant.3791124 http://pending.schema.org/fundedItem sg:pub.10.1007/978-3-642-40450-4_28
    109 rdf:type schema:MonetaryGrant
    110 sg:person.010360414373.45 schema:affiliation Ndbdb208ca9d74f5d8348cce1de91088b
    111 schema:familyName Doerr
    112 schema:givenName Carola
    113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010360414373.45
    114 rdf:type schema:Person
    115 sg:person.010366026047.55 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    116 schema:familyName Pasquale
    117 schema:givenName Francesco
    118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010366026047.55
    119 rdf:type schema:Person
    120 sg:person.01074702127.76 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    121 schema:familyName Isopi
    122 schema:givenName Marco
    123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01074702127.76
    124 rdf:type schema:Person
    125 sg:person.011027660123.21 schema:affiliation https://www.grid.ac/institutes/grid.6530.0
    126 schema:familyName Clementi
    127 schema:givenName Andrea
    128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011027660123.21
    129 rdf:type schema:Person
    130 sg:person.01173734710.11 schema:affiliation https://www.grid.ac/institutes/grid.8404.8
    131 schema:familyName Crescenzi
    132 schema:givenName Pierluigi
    133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01173734710.11
    134 rdf:type schema:Person
    135 sg:person.012430640403.64 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    136 schema:familyName Silvestri
    137 schema:givenName Riccardo
    138 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012430640403.64
    139 rdf:type schema:Person
    140 sg:person.012766154071.70 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    141 schema:familyName Panconesi
    142 schema:givenName Alessandro
    143 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012766154071.70
    144 rdf:type schema:Person
    145 sg:person.013424402135.28 schema:affiliation https://www.grid.ac/institutes/grid.7452.4
    146 schema:familyName Fraigniaud
    147 schema:givenName Pierre
    148 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013424402135.28
    149 rdf:type schema:Person
    150 sg:pub.10.1007/978-3-540-70575-8_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027002019
    151 https://doi.org/10.1007/978-3-540-70575-8_11
    152 rdf:type schema:CreativeWork
    153 sg:pub.10.1007/978-3-642-02930-1_31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015749499
    154 https://doi.org/10.1007/978-3-642-02930-1_31
    155 rdf:type schema:CreativeWork
    156 sg:pub.10.1007/s00446-011-0133-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031581381
    157 https://doi.org/10.1007/s00446-011-0133-9
    158 rdf:type schema:CreativeWork
    159 https://doi.org/10.1002/rsa.3240010406 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041604066
    160 rdf:type schema:CreativeWork
    161 https://doi.org/10.1016/0166-218x(85)90059-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006274177
    162 rdf:type schema:CreativeWork
    163 https://doi.org/10.1016/j.dam.2012.10.014 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021452341
    164 rdf:type schema:CreativeWork
    165 https://doi.org/10.1016/j.jcss.2008.10.004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012670906
    166 rdf:type schema:CreativeWork
    167 https://doi.org/10.1098/rspa.2009.0456 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034339761
    168 rdf:type schema:CreativeWork
    169 https://doi.org/10.1109/infcom.2005.1498447 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094179603
    170 rdf:type schema:CreativeWork
    171 https://doi.org/10.1109/infcom.2010.5462084 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093991060
    172 rdf:type schema:CreativeWork
    173 https://doi.org/10.1109/infcom.2011.5935249 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095207416
    174 rdf:type schema:CreativeWork
    175 https://doi.org/10.1109/sfcs.2000.892324 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093211058
    176 rdf:type schema:CreativeWork
    177 https://doi.org/10.1109/tcomm.2011.020811.090163 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061558027
    178 rdf:type schema:CreativeWork
    179 https://doi.org/10.1109/tit.2010.2059830 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061652914
    180 rdf:type schema:CreativeWork
    181 https://doi.org/10.1109/tpds.2011.33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061753875
    182 rdf:type schema:CreativeWork
    183 https://doi.org/10.1137/0147013 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062840489
    184 rdf:type schema:CreativeWork
    185 https://doi.org/10.1137/090756053 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062856216
    186 rdf:type schema:CreativeWork
    187 https://doi.org/10.1137/1.9781611973075.135 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088801192
    188 rdf:type schema:CreativeWork
    189 https://doi.org/10.1137/1.9781611973082.37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088801356
    190 rdf:type schema:CreativeWork
    191 https://doi.org/10.1137/1.9781611973099.129 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088801412
    192 rdf:type schema:CreativeWork
    193 https://doi.org/10.1137/1.9781611973099.130 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088801465
    194 rdf:type schema:CreativeWork
    195 https://doi.org/10.1137/s0097539795288490 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880047
    196 rdf:type schema:CreativeWork
    197 https://doi.org/10.1145/1275517.1275520 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020884413
    198 rdf:type schema:CreativeWork
    199 https://doi.org/10.1145/1317379.1317381 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024688335
    200 rdf:type schema:CreativeWork
    201 https://doi.org/10.1145/1806689.1806760 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046808496
    202 rdf:type schema:CreativeWork
    203 https://doi.org/10.1145/1959045.1959064 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043459609
    204 rdf:type schema:CreativeWork
    205 https://doi.org/10.1145/301308.301362 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043953521
    206 rdf:type schema:CreativeWork
    207 https://doi.org/10.1145/41840.41841 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022752417
    208 rdf:type schema:CreativeWork
    209 https://doi.org/10.1214/aoms/1177706098 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064400899
    210 rdf:type schema:CreativeWork
    211 https://www.grid.ac/institutes/grid.6530.0 schema:alternateName University of Rome Tor Vergata
    212 schema:name Università Tor Vergata di Roma, Italy
    213 rdf:type schema:Organization
    214 https://www.grid.ac/institutes/grid.7452.4 schema:alternateName Paris Diderot University
    215 schema:name CNRS and Université Paris Diderot, France
    216 rdf:type schema:Organization
    217 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
    218 schema:name Sapienza Università di Roma, Italy
    219 rdf:type schema:Organization
    220 https://www.grid.ac/institutes/grid.8404.8 schema:alternateName University of Florence
    221 schema:name Università di Firenze, Italy
    222 rdf:type schema:Organization
     




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


    ...