Efficiently Testing $$T$$ -Interval Connectivity in Dynamic Graphs View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2015

AUTHORS

Arnaud Casteigts , Ralf Klasing , Yessin M. Neggaz , Joseph G. Peters

ABSTRACT

Many types of dynamic networks are made up of durable entities whose links evolve over time. When considered from a global and discrete standpoint, these networks are often modelled as evolving graphs, i.e. a sequence of static graphs \(\mathcal{{G}}=\{G_1,G_2,...,G_{\delta }\}\) such that \(G_i=(V,E_i)\) represents the network topology at time step \(i\). Such a sequence is said to be \(T\)-interval connected if for any \(t\in [1, \delta -T+1]\) all graphs in \(\{G_t,G_{t+1},...,G_{t+T-1}\}\) share a common connected spanning subgraph. In this paper, we consider the problem of deciding whether a given sequence \(\mathcal{{G}}\) is \(T\)-interval connected for a given \(T\). We also consider the related problem of finding the largest \(T\) for which a given \(\mathcal{{G}}\) is \(T\)-interval connected. We assume that the changes between two consecutive graphs are arbitrary, and that two operations, binary intersection and connectivity testing, are available to solve the problems. We show that \(\varOmega (\delta )\) such operations are required to solve both problems, and we present optimal \(O(\delta )\) online algorithms for both problems. More... »

PAGES

89-100

References to SciGraph publications

  • 2010. Characterizing Topological Assumptions of Distributed Algorithms in Dynamic Networks in STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY
  • Book

    TITLE

    Algorithms and Complexity

    ISBN

    978-3-319-18172-1
    978-3-319-18173-8

    Author Affiliations

    From Grant

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-319-18173-8_6

    DOI

    http://dx.doi.org/10.1007/978-3-319-18173-8_6

    DIMENSIONS

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


    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": {
              "name": [
                "LaBRI, CNRS, University of Bordeaux, Talence, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Casteigts", 
            "givenName": "Arnaud", 
            "id": "sg:person.014046062661.61", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014046062661.61"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "LaBRI, CNRS, University of Bordeaux, Talence, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Klasing", 
            "givenName": "Ralf", 
            "id": "sg:person.016012765273.46", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016012765273.46"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "LaBRI, CNRS, University of Bordeaux, Talence, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Neggaz", 
            "givenName": "Yessin M.", 
            "id": "sg:person.012743642445.24", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012743642445.24"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Simon Fraser University", 
              "id": "https://www.grid.ac/institutes/grid.61971.38", 
              "name": [
                "School of Computing Science, Simon Fraser University, Burnaby, BC, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Peters", 
            "givenName": "Joseph G.", 
            "id": "sg:person.015627506034.65", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015627506034.65"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1080/17445760.2012.668546", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005693413"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0377-2217(89)90126-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006090103"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0377-2217(89)90126-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006090103"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-11476-2_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021306868", 
              "https://doi.org/10.1007/978-3-642-11476-2_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-11476-2_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021306868", 
              "https://doi.org/10.1007/978-3-642-11476-2_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1015467.1015484", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042134783"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2348543.2348589", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045787074"
            ], 
            "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.1142/s0129054103001728", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062896465"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2015", 
        "datePublishedReg": "2015-01-01", 
        "description": "Many types of dynamic networks are made up of durable entities whose links evolve over time. When considered from a global and discrete standpoint, these networks are often modelled as evolving graphs, i.e. a sequence of static graphs \\(\\mathcal{{G}}=\\{G_1,G_2,...,G_{\\delta }\\}\\) such that \\(G_i=(V,E_i)\\) represents the network topology at time step \\(i\\). Such a sequence is said to be \\(T\\)-interval connected if for any \\(t\\in [1, \\delta -T+1]\\) all graphs in \\(\\{G_t,G_{t+1},...,G_{t+T-1}\\}\\) share a common connected spanning subgraph. In this paper, we consider the problem of deciding whether a given sequence \\(\\mathcal{{G}}\\) is \\(T\\)-interval connected for a given \\(T\\). We also consider the related problem of finding the largest \\(T\\) for which a given \\(\\mathcal{{G}}\\) is \\(T\\)-interval connected. We assume that the changes between two consecutive graphs are arbitrary, and that two operations, binary intersection and connectivity testing, are available to solve the problems. We show that \\(\\varOmega (\\delta )\\) such operations are required to solve both problems, and we present optimal \\(O(\\delta )\\) online algorithms for both problems.", 
        "editor": [
          {
            "familyName": "Paschos", 
            "givenName": "Vangelis Th.", 
            "type": "Person"
          }, 
          {
            "familyName": "Widmayer", 
            "givenName": "Peter", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-319-18173-8_6", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.4523825", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": {
          "isbn": [
            "978-3-319-18172-1", 
            "978-3-319-18173-8"
          ], 
          "name": "Algorithms and Complexity", 
          "type": "Book"
        }, 
        "name": "Efficiently Testing $$T$$ -Interval Connectivity in Dynamic Graphs", 
        "pagination": "89-100", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-319-18173-8_6"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "83c6b5daf0da060e4a0d7ce5832af730c4bac31b63473ea1efe82faa7fa01ba4"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1027662009"
            ]
          }
        ], 
        "publisher": {
          "location": "Cham", 
          "name": "Springer International Publishing", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-319-18173-8_6", 
          "https://app.dimensions.ai/details/publication/pub.1027662009"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T12:32", 
        "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_8663_00000260.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-319-18173-8_6"
      }
    ]
     

    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-319-18173-8_6'

    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-319-18173-8_6'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-18173-8_6'

    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-319-18173-8_6'


     

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

    121 TRIPLES      23 PREDICATES      34 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-319-18173-8_6 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Ne6383e967bf74139bd10762757b88176
    4 schema:citation sg:pub.10.1007/978-3-642-11476-2_11
    5 https://doi.org/10.1016/0377-2217(89)90126-4
    6 https://doi.org/10.1080/17445760.2012.668546
    7 https://doi.org/10.1142/s0129054103001728
    8 https://doi.org/10.1145/1015467.1015484
    9 https://doi.org/10.1145/1806689.1806760
    10 https://doi.org/10.1145/2348543.2348589
    11 schema:datePublished 2015
    12 schema:datePublishedReg 2015-01-01
    13 schema:description Many types of dynamic networks are made up of durable entities whose links evolve over time. When considered from a global and discrete standpoint, these networks are often modelled as evolving graphs, i.e. a sequence of static graphs \(\mathcal{{G}}=\{G_1,G_2,...,G_{\delta }\}\) such that \(G_i=(V,E_i)\) represents the network topology at time step \(i\). Such a sequence is said to be \(T\)-interval connected if for any \(t\in [1, \delta -T+1]\) all graphs in \(\{G_t,G_{t+1},...,G_{t+T-1}\}\) share a common connected spanning subgraph. In this paper, we consider the problem of deciding whether a given sequence \(\mathcal{{G}}\) is \(T\)-interval connected for a given \(T\). We also consider the related problem of finding the largest \(T\) for which a given \(\mathcal{{G}}\) is \(T\)-interval connected. We assume that the changes between two consecutive graphs are arbitrary, and that two operations, binary intersection and connectivity testing, are available to solve the problems. We show that \(\varOmega (\delta )\) such operations are required to solve both problems, and we present optimal \(O(\delta )\) online algorithms for both problems.
    14 schema:editor Neebebc68c1ea463c9b3de97fa7c422cb
    15 schema:genre chapter
    16 schema:inLanguage en
    17 schema:isAccessibleForFree true
    18 schema:isPartOf N1bd0bbfb863343df909672686d6f971f
    19 schema:name Efficiently Testing $$T$$ -Interval Connectivity in Dynamic Graphs
    20 schema:pagination 89-100
    21 schema:productId N2652fb24bd7940f09b7a861040c26fa8
    22 N81a3c024ab1b40c1a13fb8e2e0bf50d8
    23 Nae4ca7772e5f49a1bd31262e0ab7fb2b
    24 schema:publisher N780d4307712c485a82df1c0146954cdc
    25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027662009
    26 https://doi.org/10.1007/978-3-319-18173-8_6
    27 schema:sdDatePublished 2019-04-15T12:32
    28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    29 schema:sdPublisher N7ff22f9c9b93441a979020d43228dcc5
    30 schema:url http://link.springer.com/10.1007/978-3-319-18173-8_6
    31 sgo:license sg:explorer/license/
    32 sgo:sdDataset chapters
    33 rdf:type schema:Chapter
    34 N1bd0bbfb863343df909672686d6f971f schema:isbn 978-3-319-18172-1
    35 978-3-319-18173-8
    36 schema:name Algorithms and Complexity
    37 rdf:type schema:Book
    38 N2652fb24bd7940f09b7a861040c26fa8 schema:name doi
    39 schema:value 10.1007/978-3-319-18173-8_6
    40 rdf:type schema:PropertyValue
    41 N41e82e3c13964e2d898f3f75348e07aa schema:familyName Paschos
    42 schema:givenName Vangelis Th.
    43 rdf:type schema:Person
    44 N5b64215ddef345fba9d3560cd708eb68 schema:name LaBRI, CNRS, University of Bordeaux, Talence, France
    45 rdf:type schema:Organization
    46 N6213fead5d0547d5ab17812119094540 rdf:first sg:person.016012765273.46
    47 rdf:rest Nf13d09405d544edc90d50df169e1672a
    48 N6cc566bd240641f1aaa8a601ca3937aa schema:familyName Widmayer
    49 schema:givenName Peter
    50 rdf:type schema:Person
    51 N780d4307712c485a82df1c0146954cdc schema:location Cham
    52 schema:name Springer International Publishing
    53 rdf:type schema:Organisation
    54 N7f38da63133648059a5c592e9f4524aa rdf:first sg:person.015627506034.65
    55 rdf:rest rdf:nil
    56 N7ff22f9c9b93441a979020d43228dcc5 schema:name Springer Nature - SN SciGraph project
    57 rdf:type schema:Organization
    58 N81a3c024ab1b40c1a13fb8e2e0bf50d8 schema:name readcube_id
    59 schema:value 83c6b5daf0da060e4a0d7ce5832af730c4bac31b63473ea1efe82faa7fa01ba4
    60 rdf:type schema:PropertyValue
    61 N84801645f6884411b80de2be1f002f2a schema:name LaBRI, CNRS, University of Bordeaux, Talence, France
    62 rdf:type schema:Organization
    63 Nae4ca7772e5f49a1bd31262e0ab7fb2b schema:name dimensions_id
    64 schema:value pub.1027662009
    65 rdf:type schema:PropertyValue
    66 Nc34eeaef2b614cebaefb88d5cfa3a765 rdf:first N6cc566bd240641f1aaa8a601ca3937aa
    67 rdf:rest rdf:nil
    68 Nc6d411666d71432f8dc09cda9d833e00 schema:name LaBRI, CNRS, University of Bordeaux, Talence, France
    69 rdf:type schema:Organization
    70 Ne6383e967bf74139bd10762757b88176 rdf:first sg:person.014046062661.61
    71 rdf:rest N6213fead5d0547d5ab17812119094540
    72 Neebebc68c1ea463c9b3de97fa7c422cb rdf:first N41e82e3c13964e2d898f3f75348e07aa
    73 rdf:rest Nc34eeaef2b614cebaefb88d5cfa3a765
    74 Nf13d09405d544edc90d50df169e1672a rdf:first sg:person.012743642445.24
    75 rdf:rest N7f38da63133648059a5c592e9f4524aa
    76 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    77 schema:name Information and Computing Sciences
    78 rdf:type schema:DefinedTerm
    79 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    80 schema:name Computation Theory and Mathematics
    81 rdf:type schema:DefinedTerm
    82 sg:grant.4523825 http://pending.schema.org/fundedItem sg:pub.10.1007/978-3-319-18173-8_6
    83 rdf:type schema:MonetaryGrant
    84 sg:person.012743642445.24 schema:affiliation N5b64215ddef345fba9d3560cd708eb68
    85 schema:familyName Neggaz
    86 schema:givenName Yessin M.
    87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012743642445.24
    88 rdf:type schema:Person
    89 sg:person.014046062661.61 schema:affiliation N84801645f6884411b80de2be1f002f2a
    90 schema:familyName Casteigts
    91 schema:givenName Arnaud
    92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014046062661.61
    93 rdf:type schema:Person
    94 sg:person.015627506034.65 schema:affiliation https://www.grid.ac/institutes/grid.61971.38
    95 schema:familyName Peters
    96 schema:givenName Joseph G.
    97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015627506034.65
    98 rdf:type schema:Person
    99 sg:person.016012765273.46 schema:affiliation Nc6d411666d71432f8dc09cda9d833e00
    100 schema:familyName Klasing
    101 schema:givenName Ralf
    102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016012765273.46
    103 rdf:type schema:Person
    104 sg:pub.10.1007/978-3-642-11476-2_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021306868
    105 https://doi.org/10.1007/978-3-642-11476-2_11
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1016/0377-2217(89)90126-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006090103
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1080/17445760.2012.668546 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005693413
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1142/s0129054103001728 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062896465
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1145/1015467.1015484 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042134783
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1145/1806689.1806760 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046808496
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1145/2348543.2348589 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045787074
    118 rdf:type schema:CreativeWork
    119 https://www.grid.ac/institutes/grid.61971.38 schema:alternateName Simon Fraser University
    120 schema:name School of Computing Science, Simon Fraser University, Burnaby, BC, Canada
    121 rdf:type schema:Organization
     




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


    ...