20 citations · 71 across the 26 of their papers we have counts for
Showing 2018Show all
3 papers · 1 filter
cs.DS2018★ 4 cited
Fully Dynamic Effective Resistances
David Durfee, Yu Gao, Gramoz Goranci +1
In this paper we consider the \emph{fully-dynamic} All-Pairs Effective Resistance problem, where the goal is to maintain effective resistances on a graph among any pair of quer…
cs.DS2018★ 20 cited
Dynamic Low-Stretch Trees via Dynamic Low-Diameter Decompositions
Sebastian Forster, Gramoz Goranci
Spanning trees of low average stretch on the non-tree edges, as introduced by Alon et al. [SICOMP 1995], are a natural graph-theoretic object. In recent years, they have found sign…
cs.DS2018
Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs
Gramoz Goranci, Monika Henzinger, Pan Peng
We consider the problem of dynamically maintaining (approximate) all-pairs effective resistances in separable graphs, which are those that admit an -separator theorem for so…