Average case analysis of fully dynamic connectivity for directed graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1994

AUTHORS

Paola Alimonti , Stefano Leonardi , Alberto Marchetti-Spacccamela , Xavier Messeguer

ABSTRACT

In this paper we consider the problem of maintaining the transitive closure in a directed graph under both edge insertions and deletions from the point of view of average case analysis. Say n the number of nodes and m the number of edges. We present a data structure that supports the report of a path between two nodes in O(n · log n) expected time and O(1) amortized time per update, and connectivity queries in a dense graph in O(1) expected time and O(n · log n) expected amortized time per update. If m > n4/3 then connectivity queries can be performed in O(1) expected time and O(log3 n) expected amortized time per update. These bounds compares favorably with the best bounds known using worst case analysis. Moreover we consider an intermediate model beetween worst case analysis and average case analysis, the semi-random adversary introduced in [2]. More... »

PAGES

87-98

Book

TITLE

Graph-Theoretic Concepts in Computer Science

ISBN

978-3-540-57899-4
978-3-540-48385-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-57899-4_43

DOI

http://dx.doi.org/10.1007/3-540-57899-4_43

DIMENSIONS

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


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": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Dipartimento di Informatica e Sistemistica, Universit\u00e0 di Roma \u201cLa Sapienza\u201d, via Salaria 113, 00198\u00a0Roma, Italia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Alimonti", 
        "givenName": "Paola", 
        "id": "sg:person.015632520461.69", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015632520461.69"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Dipartimento di Informatica e Sistemistica, Universit\u00e0 di Roma \u201cLa Sapienza\u201d, via Salaria 113, 00198\u00a0Roma, Italia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Leonardi", 
        "givenName": "Stefano", 
        "id": "sg:person.012466562455.21", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012466562455.21"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Dipartimento di Informatica e Sistemistica, Universit\u00e0 di Roma \u201cLa Sapienza\u201d, via Salaria 113, 00198\u00a0Roma, Italia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Marchetti-Spacccamela", 
        "givenName": "Alberto", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Universitat Polit\u00e8cnica de Catalunya", 
          "id": "https://www.grid.ac/institutes/grid.6835.8", 
          "name": [
            "Departament de Llenguatges i Sistemes Inform\u00e1tics, Universitat Polit\u00e9cnica de Catalunya, Pau Gargallo 5, 08028\u00a0Barcelona, Espa\u00f1a"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Messeguer", 
        "givenName": "Xavier", 
        "id": "sg:person.01022533716.38", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01022533716.38"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0304-3975(86)90098-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004552776"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(86)90098-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004552776"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/62.2160", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006789528"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(88)90136-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008898730"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/103418.103454", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013145896"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/122413.122416", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037415572"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0196-6774(91)90036-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040575736"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-0000(86)90044-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041170158"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/fscs.1990.89576", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086321380"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1994", 
    "datePublishedReg": "1994-01-01", 
    "description": "In this paper we consider the problem of maintaining the transitive closure in a directed graph under both edge insertions and deletions from the point of view of average case analysis. Say n the number of nodes and m the number of edges. We present a data structure that supports the report of a path between two nodes in O(n \u00b7 log n) expected time and O(1) amortized time per update, and connectivity queries in a dense graph in O(1) expected time and O(n \u00b7 log n) expected amortized time per update. If m > n4/3 then connectivity queries can be performed in O(1) expected time and O(log3 n) expected amortized time per update. These bounds compares favorably with the best bounds known using worst case analysis. Moreover we consider an intermediate model beetween worst case analysis and average case analysis, the semi-random adversary introduced in [2].", 
    "editor": [
      {
        "familyName": "Leeuwen", 
        "givenName": "Jan", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-57899-4_43", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-57899-4", 
        "978-3-540-48385-4"
      ], 
      "name": "Graph-Theoretic Concepts in Computer Science", 
      "type": "Book"
    }, 
    "name": "Average case analysis of fully dynamic connectivity for directed graphs", 
    "pagination": "87-98", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-57899-4_43"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "0392b087a998b9e07772ae5e2e35faca3c8e291c222ee795719e4ce165035592"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1000750289"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-57899-4_43", 
      "https://app.dimensions.ai/details/publication/pub.1000750289"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T16:50", 
    "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_8675_00000557.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-57899-4_43"
  }
]
 

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/3-540-57899-4_43'

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/3-540-57899-4_43'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-57899-4_43'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-57899-4_43'


 

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

112 TRIPLES      23 PREDICATES      35 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-57899-4_43 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nabb8fcbbcd214cf584f469e08bad1083
4 schema:citation https://doi.org/10.1016/0020-0190(88)90136-6
5 https://doi.org/10.1016/0022-0000(86)90044-9
6 https://doi.org/10.1016/0196-6774(91)90036-x
7 https://doi.org/10.1016/0304-3975(86)90098-8
8 https://doi.org/10.1109/fscs.1990.89576
9 https://doi.org/10.1145/103418.103454
10 https://doi.org/10.1145/122413.122416
11 https://doi.org/10.1145/62.2160
12 schema:datePublished 1994
13 schema:datePublishedReg 1994-01-01
14 schema:description In this paper we consider the problem of maintaining the transitive closure in a directed graph under both edge insertions and deletions from the point of view of average case analysis. Say n the number of nodes and m the number of edges. We present a data structure that supports the report of a path between two nodes in O(n · log n) expected time and O(1) amortized time per update, and connectivity queries in a dense graph in O(1) expected time and O(n · log n) expected amortized time per update. If m > n4/3 then connectivity queries can be performed in O(1) expected time and O(log3 n) expected amortized time per update. These bounds compares favorably with the best bounds known using worst case analysis. Moreover we consider an intermediate model beetween worst case analysis and average case analysis, the semi-random adversary introduced in [2].
15 schema:editor N0ac4d358706447da8390a6172737162b
16 schema:genre chapter
17 schema:inLanguage en
18 schema:isAccessibleForFree false
19 schema:isPartOf N7dbeb7b931ab4b87a90d7e095f4f74c7
20 schema:name Average case analysis of fully dynamic connectivity for directed graphs
21 schema:pagination 87-98
22 schema:productId N89fab9293f954efeb2e22e9a4c0eab62
23 Na84822304b4e4d779d0fffcf62a6ce24
24 Ncd2392adf34e40918cc096b430f05e09
25 schema:publisher N2d9fade5703745d5bdae52d2b477de43
26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000750289
27 https://doi.org/10.1007/3-540-57899-4_43
28 schema:sdDatePublished 2019-04-15T16:50
29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
30 schema:sdPublisher N190a0877a35044b194d280750ea3b741
31 schema:url http://link.springer.com/10.1007/3-540-57899-4_43
32 sgo:license sg:explorer/license/
33 sgo:sdDataset chapters
34 rdf:type schema:Chapter
35 N0ac4d358706447da8390a6172737162b rdf:first N8de16395851c411dade8a3627cd8c15c
36 rdf:rest rdf:nil
37 N190a0877a35044b194d280750ea3b741 schema:name Springer Nature - SN SciGraph project
38 rdf:type schema:Organization
39 N2d9fade5703745d5bdae52d2b477de43 schema:location Berlin, Heidelberg
40 schema:name Springer Berlin Heidelberg
41 rdf:type schema:Organisation
42 N42607c7880674753bafb080153856b25 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
43 schema:familyName Marchetti-Spacccamela
44 schema:givenName Alberto
45 rdf:type schema:Person
46 N7dbeb7b931ab4b87a90d7e095f4f74c7 schema:isbn 978-3-540-48385-4
47 978-3-540-57899-4
48 schema:name Graph-Theoretic Concepts in Computer Science
49 rdf:type schema:Book
50 N89fab9293f954efeb2e22e9a4c0eab62 schema:name readcube_id
51 schema:value 0392b087a998b9e07772ae5e2e35faca3c8e291c222ee795719e4ce165035592
52 rdf:type schema:PropertyValue
53 N8de16395851c411dade8a3627cd8c15c schema:familyName Leeuwen
54 schema:givenName Jan
55 rdf:type schema:Person
56 N9c83000e127142d2a02abef209fd0d81 rdf:first sg:person.01022533716.38
57 rdf:rest rdf:nil
58 Na84822304b4e4d779d0fffcf62a6ce24 schema:name dimensions_id
59 schema:value pub.1000750289
60 rdf:type schema:PropertyValue
61 Nabb8fcbbcd214cf584f469e08bad1083 rdf:first sg:person.015632520461.69
62 rdf:rest Ncdf3bd100ac847f9af6c58e27eb872cb
63 Ncd2392adf34e40918cc096b430f05e09 schema:name doi
64 schema:value 10.1007/3-540-57899-4_43
65 rdf:type schema:PropertyValue
66 Ncdf3bd100ac847f9af6c58e27eb872cb rdf:first sg:person.012466562455.21
67 rdf:rest Nf471f8da40824d2094051d99688ccee7
68 Nf471f8da40824d2094051d99688ccee7 rdf:first N42607c7880674753bafb080153856b25
69 rdf:rest N9c83000e127142d2a02abef209fd0d81
70 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
71 schema:name Information and Computing Sciences
72 rdf:type schema:DefinedTerm
73 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
74 schema:name Computation Theory and Mathematics
75 rdf:type schema:DefinedTerm
76 sg:person.01022533716.38 schema:affiliation https://www.grid.ac/institutes/grid.6835.8
77 schema:familyName Messeguer
78 schema:givenName Xavier
79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01022533716.38
80 rdf:type schema:Person
81 sg:person.012466562455.21 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
82 schema:familyName Leonardi
83 schema:givenName Stefano
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012466562455.21
85 rdf:type schema:Person
86 sg:person.015632520461.69 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
87 schema:familyName Alimonti
88 schema:givenName Paola
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015632520461.69
90 rdf:type schema:Person
91 https://doi.org/10.1016/0020-0190(88)90136-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008898730
92 rdf:type schema:CreativeWork
93 https://doi.org/10.1016/0022-0000(86)90044-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041170158
94 rdf:type schema:CreativeWork
95 https://doi.org/10.1016/0196-6774(91)90036-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1040575736
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1016/0304-3975(86)90098-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004552776
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1109/fscs.1990.89576 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086321380
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1145/103418.103454 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013145896
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1145/122413.122416 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037415572
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1145/62.2160 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006789528
106 rdf:type schema:CreativeWork
107 https://www.grid.ac/institutes/grid.6835.8 schema:alternateName Universitat Politècnica de Catalunya
108 schema:name Departament de Llenguatges i Sistemes Informátics, Universitat Politécnica de Catalunya, Pau Gargallo 5, 08028 Barcelona, España
109 rdf:type schema:Organization
110 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
111 schema:name Dipartimento di Informatica e Sistemistica, Università di Roma “La Sapienza”, via Salaria 113, 00198 Roma, Italia
112 rdf:type schema:Organization
 




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


...