---
res:
  bibo_abstract:
  - "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.\r\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.\r\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.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Gramoz
      foaf_name: Goranci, Gramoz
      foaf_surname: Goranci
  - foaf_Person:
      foaf_givenName: Monika H
      foaf_name: Henzinger, Monika H
      foaf_surname: Henzinger
      foaf_workInfoHomepage: http://www.librecat.org/personId=540c9bbd-f2de-11ec-812d-d04a5be85630
    orcid: 0000-0002-5008-6530
  - foaf_Person:
      foaf_givenName: Pan
      foaf_name: Peng, Pan
      foaf_surname: Peng
  bibo_doi: 10.4230/LIPICS.ESA.2018.40
  bibo_volume: 112
  dct_date: 2018^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/1868-8969
  - http://id.crossref.org/issn/9783959770811
  dct_language: eng
  dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
  dct_title: Dynamic effective resistances and approximate schur complement on separable
    graphs@
...