scientific article; zbMATH DE number 7378710

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.

zbMATH Keywords

Schur complementeffective resistancedynamic graph algorithmsconditional lower boundsseparable graphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

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: