---
_id: '11828'
abstract:
- lang: eng
  text: "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."
alternative_title:
- LIPIcs
article_number: '40'
article_processing_charge: No
arxiv: 1
author:
- first_name: Gramoz
  full_name: Goranci, Gramoz
  last_name: Goranci
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Pan
  full_name: Peng, Pan
  last_name: Peng
citation:
  ama: 'Goranci G, Henzinger M, Peng P. Dynamic effective resistances and approximate
    schur complement on separable graphs. In: <i>26th Annual European Symposium on
    Algorithms</i>. Vol 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018.
    doi:<a href="https://doi.org/10.4230/LIPICS.ESA.2018.40">10.4230/LIPICS.ESA.2018.40</a>'
  apa: 'Goranci, G., Henzinger, M., &#38; Peng, P. (2018). Dynamic effective resistances
    and approximate schur complement on separable graphs. In <i>26th Annual European
    Symposium on Algorithms</i> (Vol. 112). Helsinki, Finland: Schloss Dagstuhl -
    Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPICS.ESA.2018.40">https://doi.org/10.4230/LIPICS.ESA.2018.40</a>'
  chicago: Goranci, Gramoz, Monika Henzinger, and Pan Peng. “Dynamic Effective Resistances
    and Approximate Schur Complement on Separable Graphs.” In <i>26th Annual European
    Symposium on Algorithms</i>, Vol. 112. Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik, 2018. <a href="https://doi.org/10.4230/LIPICS.ESA.2018.40">https://doi.org/10.4230/LIPICS.ESA.2018.40</a>.
  ieee: G. Goranci, M. Henzinger, and P. Peng, “Dynamic effective resistances and
    approximate schur complement on separable graphs,” in <i>26th Annual European
    Symposium on Algorithms</i>, Helsinki, Finland, 2018, vol. 112.
  ista: 'Goranci G, Henzinger M, Peng P. 2018. Dynamic effective resistances and approximate
    schur complement on separable graphs. 26th Annual European Symposium on Algorithms.
    ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 112, 40.'
  mla: Goranci, Gramoz, et al. “Dynamic Effective Resistances and Approximate Schur
    Complement on Separable Graphs.” <i>26th Annual European Symposium on Algorithms</i>,
    vol. 112, 40, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:<a
    href="https://doi.org/10.4230/LIPICS.ESA.2018.40">10.4230/LIPICS.ESA.2018.40</a>.
  short: G. Goranci, M. Henzinger, P. Peng, in:, 26th Annual European Symposium on
    Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
conference:
  end_date: 2018-08-22
  location: Helsinki, Finland
  name: 'ESA: Annual European Symposium on Algorithms'
  start_date: 2018-08-20
corr_author: '1'
date_created: 2022-08-12T08:26:42Z
date_published: 2018-08-14T00:00:00Z
date_updated: 2024-11-06T12:16:31Z
day: '14'
doi: 10.4230/LIPICS.ESA.2018.40
extern: '1'
external_id:
  arxiv:
  - '1802.09111'
intvolume: '       112'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.4230/LIPIcs.ESA.2018.40
month: '08'
oa: 1
oa_version: Published Version
publication: 26th Annual European Symposium on Algorithms
publication_identifier:
  isbn:
  - '9783959770811'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dynamic effective resistances and approximate schur complement on separable
  graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 112
year: '2018'
...