Fully dynamic spectral vertex sparsifiers and applications

DOI10.1145/3313276.3316379zbMath1433.68291arXiv1906.10530OpenAlexW2964343692MaRDI QIDQ5212832

Gramoz Goranci, Yu Gao, David Durfee, Richard Peng

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1906.10530

zbMATH Keywords

Schur complementeffective resistancegraph Laplaciandynamic graph algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory to circuits and networks (94C15) Data structures (68P05)

Related Items (3)

Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts ⋮ Unnamed Item ⋮ Sublinear update time randomized algorithms for dynamic graph regression

This page was built for publication: Fully dynamic spectral vertex sparsifiers and applications