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 N4d5321b396db45c59cd759dbcb577c54
    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 Nbe6dd79173d64541bf216e3db17f2b17
    37 schema:genre chapter
    38 schema:inLanguage en
    39 schema:isAccessibleForFree true
    40 schema:isPartOf Nef04a1e55f174a4b890231b7ec013712
    41 schema:name Rumor Spreading in Random Evolving Graphs
    42 schema:pagination 325-336
    43 schema:productId N2ee501e1caac4a408a0d03870a886a68
    44 N4f049913417446cd9fc345b1eacfd35c
    45 Ned5770af967d4ff0a13c8286686953ac
    46 schema:publisher Nd25223fcc3d348a8abf339455b6b0752
    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 Ne35446c605da47c0ac976bfef65dca55
    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 N239eec6b169b453d9f81330cdef403df rdf:first sg:person.010366026047.55
    57 rdf:rest Nb96ea8f38fdb434ebea0465153a83e7e
    58 N2ee501e1caac4a408a0d03870a886a68 schema:name dimensions_id
    59 schema:value pub.1018567336
    60 rdf:type schema:PropertyValue
    61 N3d034f8aa7d04e43b0b7b1b8cd6d3429 rdf:first sg:person.012766154071.70
    62 rdf:rest N239eec6b169b453d9f81330cdef403df
    63 N4d5321b396db45c59cd759dbcb577c54 rdf:first sg:person.011027660123.21
    64 rdf:rest N63cc6ee41e3b4132984a56a332a15387
    65 N4d713ecc461241c99aa6b547e8832edb rdf:first sg:person.010360414373.45
    66 rdf:rest Na81a8850fcad40288cc46a6d25fd63be
    67 N4f049913417446cd9fc345b1eacfd35c schema:name readcube_id
    68 schema:value 58773dc08137b8776996f73307759e1a5b12001fd98c42a366833b6f414d4879
    69 rdf:type schema:PropertyValue
    70 N598e71e5709340a686a40fd6ec2d0c9e schema:familyName Italiano
    71 schema:givenName Giuseppe F.
    72 rdf:type schema:Person
    73 N63cc6ee41e3b4132984a56a332a15387 rdf:first sg:person.01173734710.11
    74 rdf:rest N4d713ecc461241c99aa6b547e8832edb
    75 N812ca83279d14c21a5f229c16f491b97 rdf:first N598e71e5709340a686a40fd6ec2d0c9e
    76 rdf:rest rdf:nil
    77 Na81a8850fcad40288cc46a6d25fd63be rdf:first sg:person.013424402135.28
    78 rdf:rest Nc333754c727d434f9d1167fe6bfcb016
    79 Nb96ea8f38fdb434ebea0465153a83e7e rdf:first sg:person.012430640403.64
    80 rdf:rest rdf:nil
    81 Nbe6dd79173d64541bf216e3db17f2b17 rdf:first Necd97a02336b4d75b76ed3f46c70acba
    82 rdf:rest N812ca83279d14c21a5f229c16f491b97
    83 Nbf6820ce01e545a08c7c47d103bbbd10 schema:name Université Paris Diderot and Max Planck Institute Saarbrücken, Germany
    84 rdf:type schema:Organization
    85 Nc333754c727d434f9d1167fe6bfcb016 rdf:first sg:person.01074702127.76
    86 rdf:rest N3d034f8aa7d04e43b0b7b1b8cd6d3429
    87 Nd25223fcc3d348a8abf339455b6b0752 schema:location Berlin, Heidelberg
    88 schema:name Springer Berlin Heidelberg
    89 rdf:type schema:Organisation
    90 Ne35446c605da47c0ac976bfef65dca55 schema:name Springer Nature - SN SciGraph project
    91 rdf:type schema:Organization
    92 Necd97a02336b4d75b76ed3f46c70acba schema:familyName Bodlaender
    93 schema:givenName Hans L.
    94 rdf:type schema:Person
    95 Ned5770af967d4ff0a13c8286686953ac schema:name doi
    96 schema:value 10.1007/978-3-642-40450-4_28
    97 rdf:type schema:PropertyValue
    98 Nef04a1e55f174a4b890231b7ec013712 schema:isbn 978-3-642-40449-8
    99 978-3-642-40450-4
    100 schema:name Algorithms – ESA 2013
    101 rdf:type schema:Book
    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 Nbf6820ce01e545a08c7c47d103bbbd10
    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)


    ...