---
res:
  bibo_abstract:
  - "We introduce a new algorithmic framework for designing dynamic graph algorithms
    in minor-free graphs, by exploiting the structure of such graphs and a tool called
    vertex sparsification, which is a way to compress large graphs into small ones
    that well preserve relevant properties among a subset of vertices and has previously
    mainly been used in the design of approximation algorithms.\r\n\r\nUsing this
    framework, we obtain a Monte Carlo randomized fully dynamic algorithm for (1 +
    epsilon)-approximating the energy of electrical flows in n-vertex planar graphs
    with tilde{O}(r epsilon^{-2}) worst-case update time and tilde{O}((r + n / sqrt{r})
    epsilon^{-2}) worst-case query time, for any r larger than some constant. For
    r=n^{2/3}, this gives tilde{O}(n^{2/3} epsilon^{-2}) update time and tilde{O}(n^{2/3}
    epsilon^{-2}) query time. We also extend this algorithm to work for minor-free
    graphs with similar approximation and running time guarantees. Furthermore, we
    illustrate our framework on the all-pairs max flow and shortest path problems
    by giving corresponding dynamic algorithms in minor-free graphs with both sublinear
    update and query times. To the best of our knowledge, our results are the first
    to systematically establish such a connection between dynamic graph algorithms
    and vertex sparsification.\r\n\r\nWe also present both upper bound and lower bound
    for maintaining the energy of electrical flows in the incremental subgraph model,
    where updates consist of only vertex activations, which might be of independent
    interest.@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.2017.45
  bibo_volume: 87
  dct_date: 2017^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/1868-8969
  - http://id.crossref.org/issn/978-3-95977-049-1
  dct_language: eng
  dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
  dct_title: The power of vertex sparsifiers in dynamic graph algorithms@
...