Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs Article Swipe
Gramoz Goranci
,
Monika Henzinger
,
Pan Peng
·
YOU?
·
· 2018
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.esa.2018.40
YOU?
·
· 2018
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.esa.2018.40
We consider the problem of dynamically maintaining (approximate) all-pairs effective resistances in separable graphs, which are those that admit an n^{c}-separator theorem for some c<1. We give a fully dynamic algorithm that maintains (1+epsilon)-approximations of the all-pairs effective resistances of an n-vertex graph G undergoing edge insertions and deletions with O~(sqrt{n}/epsilon^2) worst-case update time and O~(sqrt{n}/epsilon^2) worst-case query time, if G is guaranteed to be sqrt{n}-separable (i.e., it is taken from a class satisfying a sqrt{n}-separator theorem) and its separator can be computed in O~(n) time. Our algorithm is built upon a dynamic algorithm for maintaining approximate Schur complement that approximately preserves pairwise effective resistances among a set of terminals for separable graphs, which might be of independent interest.\nWe complement our result by proving that for any two fixed vertices s and t, no incremental or decremental algorithm can maintain the s-t effective resistance for sqrt{n}-separable graphs with worst-case update time O(n^{1/2-delta}) and query time O(n^{1-delta}) for any delta>0, unless the Online Matrix Vector Multiplication (OMv) conjecture is false.\nWe further show that for general graphs, no incremental or decremental algorithm can maintain the s-t effective resistance problem with worst-case update time O(n^{1-delta}) and query-time O(n^{2-delta}) for any delta >0, unless the OMv conjecture is false.
Related Topics
Concepts
Combinatorics
Mathematics
Conjecture
Separable space
Complement (music)
Discrete mathematics
Chemistry
Phenotype
Complementation
Mathematical analysis
Gene
Biochemistry
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.40
- OA Status
- green
- Cited By
- 13
- Related Works
- 20
- OpenAlex ID
- https://openalex.org/W2962943905
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W2962943905Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.4230/lipics.esa.2018.40Digital Object Identifier
- Title
-
Dynamic Effective Resistances and Approximate Schur Complement on Separable GraphsWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2018Year of publication
- Publication date
-
2018-08-16Full publication date if available
- Authors
-
Gramoz Goranci, Monika Henzinger, Pan PengList of authors in order
- Landing page
-
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.40Publisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.40Direct OA link when available
- Concepts
-
Combinatorics, Mathematics, Conjecture, Separable space, Complement (music), Discrete mathematics, Chemistry, Phenotype, Complementation, Mathematical analysis, Gene, BiochemistryTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
13Total citation count in OpenAlex
- Citations by year (recent)
-
2024: 1, 2022: 2, 2021: 2, 2020: 3, 2019: 4Per-year citation counts (last 5 years)
- Related works (count)
-
20Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W2962943905 |
|---|---|
| doi | https://doi.org/10.4230/lipics.esa.2018.40 |
| ids.mag | 2962943905 |
| ids.openalex | https://openalex.org/W2962943905 |
| fwci | 2.47765924 |
| type | article |
| title | Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | 15 |
| topics[0].id | https://openalex.org/T10720 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9970999956130981 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1703 |
| topics[0].subfield.display_name | Computational Theory and Mathematics |
| topics[0].display_name | Complexity and Algorithms in Graphs |
| topics[1].id | https://openalex.org/T10772 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9943000078201294 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1705 |
| topics[1].subfield.display_name | Computer Networks and Communications |
| topics[1].display_name | Distributed systems and fault tolerance |
| topics[2].id | https://openalex.org/T11478 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9847999811172485 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1705 |
| topics[2].subfield.display_name | Computer Networks and Communications |
| topics[2].display_name | Caching and Content Delivery |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C114614502 |
| concepts[0].level | 1 |
| concepts[0].score | 0.76236891746521 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[0].display_name | Combinatorics |
| concepts[1].id | https://openalex.org/C33923547 |
| concepts[1].level | 0 |
| concepts[1].score | 0.6146838068962097 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[1].display_name | Mathematics |
| concepts[2].id | https://openalex.org/C2780990831 |
| concepts[2].level | 2 |
| concepts[2].score | 0.6001132726669312 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q319141 |
| concepts[2].display_name | Conjecture |
| concepts[3].id | https://openalex.org/C70710897 |
| concepts[3].level | 2 |
| concepts[3].score | 0.5142518877983093 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q680081 |
| concepts[3].display_name | Separable space |
| concepts[4].id | https://openalex.org/C112313634 |
| concepts[4].level | 5 |
| concepts[4].score | 0.46526291966438293 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q7886648 |
| concepts[4].display_name | Complement (music) |
| concepts[5].id | https://openalex.org/C118615104 |
| concepts[5].level | 1 |
| concepts[5].score | 0.4464949667453766 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[5].display_name | Discrete mathematics |
| concepts[6].id | https://openalex.org/C185592680 |
| concepts[6].level | 0 |
| concepts[6].score | 0.0 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q2329 |
| concepts[6].display_name | Chemistry |
| concepts[7].id | https://openalex.org/C127716648 |
| concepts[7].level | 3 |
| concepts[7].score | 0.0 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q104053 |
| concepts[7].display_name | Phenotype |
| concepts[8].id | https://openalex.org/C188082640 |
| concepts[8].level | 4 |
| concepts[8].score | 0.0 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q1780899 |
| concepts[8].display_name | Complementation |
| concepts[9].id | https://openalex.org/C134306372 |
| concepts[9].level | 1 |
| concepts[9].score | 0.0 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[9].display_name | Mathematical analysis |
| concepts[10].id | https://openalex.org/C104317684 |
| concepts[10].level | 2 |
| concepts[10].score | 0.0 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q7187 |
| concepts[10].display_name | Gene |
| concepts[11].id | https://openalex.org/C55493867 |
| concepts[11].level | 1 |
| concepts[11].score | 0.0 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q7094 |
| concepts[11].display_name | Biochemistry |
| keywords[0].id | https://openalex.org/keywords/combinatorics |
| keywords[0].score | 0.76236891746521 |
| keywords[0].display_name | Combinatorics |
| keywords[1].id | https://openalex.org/keywords/mathematics |
| keywords[1].score | 0.6146838068962097 |
| keywords[1].display_name | Mathematics |
| keywords[2].id | https://openalex.org/keywords/conjecture |
| keywords[2].score | 0.6001132726669312 |
| keywords[2].display_name | Conjecture |
| keywords[3].id | https://openalex.org/keywords/separable-space |
| keywords[3].score | 0.5142518877983093 |
| keywords[3].display_name | Separable space |
| keywords[4].id | https://openalex.org/keywords/complement |
| keywords[4].score | 0.46526291966438293 |
| keywords[4].display_name | Complement (music) |
| keywords[5].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[5].score | 0.4464949667453766 |
| keywords[5].display_name | Discrete mathematics |
| language | en |
| locations[0].id | pmh:oai:drops-oai.dagstuhl.de:9503 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306402524 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | False |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | Leibniz-Zentrum für Informatik (Schloss Dagstuhl) |
| locations[0].source.host_organization | https://openalex.org/I2799853480 |
| locations[0].source.host_organization_name | Schloss Dagstuhl – Leibniz Center for Informatics |
| locations[0].source.host_organization_lineage | https://openalex.org/I2799853480 |
| locations[0].license | cc-by |
| locations[0].pdf_url | |
| locations[0].version | publishedVersion |
| locations[0].raw_type | InProceedings |
| locations[0].license_id | https://openalex.org/licenses/cc-by |
| locations[0].is_accepted | True |
| locations[0].is_published | True |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.40 |
| locations[1].id | mag:2962943905 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | arXiv (Cornell University) |
| locations[1].landing_page_url | https://arxiv.org/pdf/1802.09111.pdf |
| authorships[0].author.id | https://openalex.org/A5078315645 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-9603-2255 |
| authorships[0].author.display_name | Gramoz Goranci |
| authorships[0].countries | AT |
| authorships[0].affiliations[0].institution_ids | https://openalex.org/I129774422 |
| authorships[0].affiliations[0].raw_affiliation_string | University of Vienna, Vienna, Austria |
| authorships[0].institutions[0].id | https://openalex.org/I129774422 |
| authorships[0].institutions[0].ror | https://ror.org/03prydq77 |
| authorships[0].institutions[0].type | education |
| authorships[0].institutions[0].lineage | https://openalex.org/I129774422 |
| authorships[0].institutions[0].country_code | AT |
| authorships[0].institutions[0].display_name | University of Vienna |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Gramoz Goranci |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | University of Vienna, Vienna, Austria |
| authorships[1].author.id | https://openalex.org/A5003641345 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-5008-6530 |
| authorships[1].author.display_name | Monika Henzinger |
| authorships[1].countries | AT |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I129774422 |
| authorships[1].affiliations[0].raw_affiliation_string | University of Vienna, Vienna, Austria |
| authorships[1].institutions[0].id | https://openalex.org/I129774422 |
| authorships[1].institutions[0].ror | https://ror.org/03prydq77 |
| authorships[1].institutions[0].type | education |
| authorships[1].institutions[0].lineage | https://openalex.org/I129774422 |
| authorships[1].institutions[0].country_code | AT |
| authorships[1].institutions[0].display_name | University of Vienna |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Monika Henzinger |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | University of Vienna, Vienna, Austria |
| authorships[2].author.id | https://openalex.org/A5101668134 |
| authorships[2].author.orcid | https://orcid.org/0000-0003-2700-5699 |
| authorships[2].author.display_name | Pan Peng |
| authorships[2].countries | GB |
| authorships[2].affiliations[0].institution_ids | https://openalex.org/I91136226 |
| authorships[2].affiliations[0].raw_affiliation_string | University of Sheffield, Sheffield, United Kingdom |
| authorships[2].institutions[0].id | https://openalex.org/I91136226 |
| authorships[2].institutions[0].ror | https://ror.org/05krs5044 |
| authorships[2].institutions[0].type | education |
| authorships[2].institutions[0].lineage | https://openalex.org/I91136226 |
| authorships[2].institutions[0].country_code | GB |
| authorships[2].institutions[0].display_name | University of Sheffield |
| authorships[2].author_position | last |
| authorships[2].raw_author_name | Pan Peng |
| authorships[2].is_corresponding | False |
| authorships[2].raw_affiliation_strings | University of Sheffield, Sheffield, United Kingdom |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.40 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs |
| has_fulltext | True |
| is_retracted | False |
| updated_date | 2025-10-10T17:16:08.811792 |
| primary_topic.id | https://openalex.org/T10720 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9970999956130981 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1703 |
| primary_topic.subfield.display_name | Computational Theory and Mathematics |
| primary_topic.display_name | Complexity and Algorithms in Graphs |
| related_works | https://openalex.org/W2787935570, https://openalex.org/W3104306072, https://openalex.org/W2964343692, https://openalex.org/W2964030863, https://openalex.org/W2066398433, https://openalex.org/W2964264613, https://openalex.org/W2963324223, https://openalex.org/W2571471359, https://openalex.org/W2565540516, https://openalex.org/W2552685338, https://openalex.org/W2150187954, https://openalex.org/W2949942456, https://openalex.org/W2941476254, https://openalex.org/W3100089996, https://openalex.org/W2964121826, https://openalex.org/W2418286382, https://openalex.org/W2129575457, https://openalex.org/W2036669621, https://openalex.org/W2950934591, https://openalex.org/W2123734400 |
| cited_by_count | 13 |
| counts_by_year[0].year | 2024 |
| counts_by_year[0].cited_by_count | 1 |
| counts_by_year[1].year | 2022 |
| counts_by_year[1].cited_by_count | 2 |
| counts_by_year[2].year | 2021 |
| counts_by_year[2].cited_by_count | 2 |
| counts_by_year[3].year | 2020 |
| counts_by_year[3].cited_by_count | 3 |
| counts_by_year[4].year | 2019 |
| counts_by_year[4].cited_by_count | 4 |
| counts_by_year[5].year | 2018 |
| counts_by_year[5].cited_by_count | 1 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:drops-oai.dagstuhl.de:9503 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306402524 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | False |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | Leibniz-Zentrum für Informatik (Schloss Dagstuhl) |
| best_oa_location.source.host_organization | https://openalex.org/I2799853480 |
| best_oa_location.source.host_organization_name | Schloss Dagstuhl – Leibniz Center for Informatics |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I2799853480 |
| best_oa_location.license | cc-by |
| best_oa_location.pdf_url | |
| best_oa_location.version | publishedVersion |
| best_oa_location.raw_type | InProceedings |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by |
| best_oa_location.is_accepted | True |
| best_oa_location.is_published | True |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.40 |
| primary_location.id | pmh:oai:drops-oai.dagstuhl.de:9503 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306402524 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | False |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | Leibniz-Zentrum für Informatik (Schloss Dagstuhl) |
| primary_location.source.host_organization | https://openalex.org/I2799853480 |
| primary_location.source.host_organization_name | Schloss Dagstuhl – Leibniz Center for Informatics |
| primary_location.source.host_organization_lineage | https://openalex.org/I2799853480 |
| primary_location.license | cc-by |
| primary_location.pdf_url | |
| primary_location.version | publishedVersion |
| primary_location.raw_type | InProceedings |
| primary_location.license_id | https://openalex.org/licenses/cc-by |
| primary_location.is_accepted | True |
| primary_location.is_published | True |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.40 |
| publication_date | 2018-08-16 |
| publication_year | 2018 |
| referenced_works_count | 0 |
| abstract_inverted_index.G | 43, 60 |
| abstract_inverted_index.a | 27, 71, 74, 91, 106 |
| abstract_inverted_index.s | 130 |
| abstract_inverted_index.We | 0, 25 |
| abstract_inverted_index.an | 19, 40 |
| abstract_inverted_index.be | 64, 81, 115 |
| abstract_inverted_index.by | 122 |
| abstract_inverted_index.if | 59 |
| abstract_inverted_index.in | 11, 83 |
| abstract_inverted_index.is | 61, 68, 88, 167, 203 |
| abstract_inverted_index.it | 67 |
| abstract_inverted_index.no | 133, 175 |
| abstract_inverted_index.of | 4, 34, 39, 108, 116 |
| abstract_inverted_index.or | 135, 177 |
| abstract_inverted_index.t, | 132 |
| abstract_inverted_index.to | 63 |
| abstract_inverted_index.OMv | 201 |
| abstract_inverted_index.Our | 86 |
| abstract_inverted_index.and | 47, 54, 77, 131, 152, 192 |
| abstract_inverted_index.any | 126, 157, 196 |
| abstract_inverted_index.are | 15 |
| abstract_inverted_index.can | 80, 138, 180 |
| abstract_inverted_index.for | 22, 94, 110, 125, 144, 156, 172, 195 |
| abstract_inverted_index.its | 78 |
| abstract_inverted_index.our | 120 |
| abstract_inverted_index.s-t | 141, 183 |
| abstract_inverted_index.set | 107 |
| abstract_inverted_index.the | 2, 35, 140, 160, 182, 200 |
| abstract_inverted_index.two | 127 |
| abstract_inverted_index.edge | 45 |
| abstract_inverted_index.from | 70 |
| abstract_inverted_index.give | 26 |
| abstract_inverted_index.show | 170 |
| abstract_inverted_index.some | 23 |
| abstract_inverted_index.that | 17, 31, 99, 124, 171 |
| abstract_inverted_index.time | 53, 150, 154, 190 |
| abstract_inverted_index.upon | 90 |
| abstract_inverted_index.with | 49, 147, 187 |
| abstract_inverted_index.(OMv) | 165 |
| abstract_inverted_index.O~(n) | 84 |
| abstract_inverted_index.Schur | 97 |
| abstract_inverted_index.admit | 18 |
| abstract_inverted_index.among | 105 |
| abstract_inverted_index.built | 89 |
| abstract_inverted_index.class | 72 |
| abstract_inverted_index.delta | 197 |
| abstract_inverted_index.fixed | 128 |
| abstract_inverted_index.fully | 28 |
| abstract_inverted_index.graph | 42 |
| abstract_inverted_index.might | 114 |
| abstract_inverted_index.query | 57, 153 |
| abstract_inverted_index.taken | 69 |
| abstract_inverted_index.those | 16 |
| abstract_inverted_index.time, | 58 |
| abstract_inverted_index.time. | 85 |
| abstract_inverted_index.which | 14, 113 |
| abstract_inverted_index.>0, | 198 |
| abstract_inverted_index.(i.e., | 66 |
| abstract_inverted_index.Matrix | 162 |
| abstract_inverted_index.Online | 161 |
| abstract_inverted_index.Vector | 163 |
| abstract_inverted_index.false. | 204 |
| abstract_inverted_index.graphs | 146 |
| abstract_inverted_index.result | 121 |
| abstract_inverted_index.unless | 159, 199 |
| abstract_inverted_index.update | 52, 149, 189 |
| abstract_inverted_index.c<1. | 24 |
| abstract_inverted_index.dynamic | 29, 92 |
| abstract_inverted_index.further | 169 |
| abstract_inverted_index.general | 173 |
| abstract_inverted_index.graphs, | 13, 112, 174 |
| abstract_inverted_index.problem | 3, 186 |
| abstract_inverted_index.proving | 123 |
| abstract_inverted_index.theorem | 21 |
| abstract_inverted_index.computed | 82 |
| abstract_inverted_index.consider | 1 |
| abstract_inverted_index.maintain | 139, 181 |
| abstract_inverted_index.n-vertex | 41 |
| abstract_inverted_index.pairwise | 102 |
| abstract_inverted_index.theorem) | 76 |
| abstract_inverted_index.vertices | 129 |
| abstract_inverted_index.algorithm | 30, 87, 93, 137, 179 |
| abstract_inverted_index.all-pairs | 8, 36 |
| abstract_inverted_index.deletions | 48 |
| abstract_inverted_index.effective | 9, 37, 103, 142, 184 |
| abstract_inverted_index.maintains | 32 |
| abstract_inverted_index.preserves | 101 |
| abstract_inverted_index.separable | 12, 111 |
| abstract_inverted_index.separator | 79 |
| abstract_inverted_index.terminals | 109 |
| abstract_inverted_index.complement | 98, 119 |
| abstract_inverted_index.conjecture | 166, 202 |
| abstract_inverted_index.false.\nWe | 168 |
| abstract_inverted_index.guaranteed | 62 |
| abstract_inverted_index.insertions | 46 |
| abstract_inverted_index.query-time | 193 |
| abstract_inverted_index.resistance | 143, 185 |
| abstract_inverted_index.satisfying | 73 |
| abstract_inverted_index.undergoing | 44 |
| abstract_inverted_index.worst-case | 51, 56, 148, 188 |
| abstract_inverted_index.approximate | 96 |
| abstract_inverted_index.decremental | 136, 178 |
| abstract_inverted_index.delta>0, | 158 |
| abstract_inverted_index.dynamically | 5 |
| abstract_inverted_index.incremental | 134, 176 |
| abstract_inverted_index.independent | 117 |
| abstract_inverted_index.maintaining | 6, 95 |
| abstract_inverted_index.resistances | 10, 38, 104 |
| abstract_inverted_index.(approximate) | 7 |
| abstract_inverted_index.approximately | 100 |
| abstract_inverted_index.interest.\nWe | 118 |
| abstract_inverted_index.Multiplication | 164 |
| abstract_inverted_index.O(n^{1-delta}) | 155, 191 |
| abstract_inverted_index.O(n^{2-delta}) | 194 |
| abstract_inverted_index.n^{c}-separator | 20 |
| abstract_inverted_index.O(n^{1/2-delta}) | 151 |
| abstract_inverted_index.sqrt{n}-separable | 65, 145 |
| abstract_inverted_index.sqrt{n}-separator | 75 |
| abstract_inverted_index.O~(sqrt{n}/epsilon^2) | 50, 55 |
| abstract_inverted_index.(1+epsilon)-approximations | 33 |
| cited_by_percentile_year.max | 98 |
| cited_by_percentile_year.min | 90 |
| countries_distinct_count | 2 |
| institutions_distinct_count | 3 |
| citation_normalized_percentile.value | 0.89345185 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | True |