scientific article; zbMATH DE number 7378710
From MaRDI portal
Publication:5009600
DOI10.4230/LIPIcs.ESA.2018.40MaRDI QIDQ5009600
Pan Peng, Gramoz Goranci, Monika R. Henzinger
Publication date: 4 August 2021
Full work available at URL: https://arxiv.org/abs/1802.09111
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Schur complementeffective resistancedynamic graph algorithmsconditional lower boundsseparable graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A fully dynamic approximation scheme for shortest paths in planar graphs
- Separator based sparsification. I: Planarity testing and minimum spanning trees
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
- Dynamic Plane Transitive Closure
- A Separator Theorem for Planar Graphs
- Generalized Nested Dissection
- A generalization of the fast LUP matrix decomposition algorithm and applications
- Separators for sphere-packings and nearest neighbor graphs
- Triangular Factorization and Inversion by Fast Matrix Multiplication
- Efficient $\widetilde{O}(n/\epsilon)$ Spectral Sketches for the Laplacian and its Pseudoinverse
- Sampling random spanning trees faster than matrix multiplication
- Decremental single-source reachability in planar digraphs
- Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
- Contracting a Planar Graph Efficiently
- Maximizing the Number of Spanning Trees in a Connected Graph
- Fully dynamic spectral vertex sparsifiers and applications
- An almost-linear time algorithm for uniform random spanning tree generation
- Solving SDD linear systems in nearly m log 1/2 n time
- Towards Resistance Sparsifiers
- Sparsified Cholesky and multigrid solvers for connection laplacians
- Fast Generation of Random Spanning Trees and the Effective Resistance Metric
- Faster approximate multicommodity flow using quadratically coupled flows
- Multiplying matrices faster than coppersmith-winograd
- Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
- Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
- Improved algorithms for min cut and max flow in undirected planar graphs
- Approximate Maximum Flow on Separable Undirected Graphs
- Graph Sparsification by Effective Resistances
This page was built for publication: