scientific article; zbMATH DE number 7205023
From MaRDI portal
Publication:5111734
DOI10.4230/LIPIcs.ESA.2017.45zbMath1442.68172arXiv1712.06473MaRDI QIDQ5111734
Gramoz Goranci, Pan Peng, Monika R. Henzinger
Publication date: 27 May 2020
Full work available at URL: https://arxiv.org/abs/1712.06473
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory to circuits and networks (94C15) Approximation algorithms (68W25) Randomized algorithms (68W20) Flows in graphs (05C21)
Related Items (max. 100)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Spectral sparsification in the semi-streaming setting
- Spanning forests and the vector bundle Laplacian
- Planar separators and parallel polygon triangulation.
- A fully dynamic approximation scheme for shortest paths in planar graphs
- Separator based sparsification. I: Planarity testing and minimum spanning trees
- Preserving Terminal Distances Using Minors
- Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
- Single Pass Spectral Sparsification in Dynamic Streams
- Fully Dynamic All-Pairs Shortest Paths: Breaking the O(n) Barrier
- Spectral Sparsification of Graphs
- Fully dynamic planarity testing with applications
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Generalized Nested Dissection
- Approximate Undirected Maximum Flows in O(mpolylog(n)) Time
- Sampling random spanning trees faster than matrix multiplication
- Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
- Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time
- An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
- Towards (1 + ∊)-Approximate Flow Sparsifiers
- Routing in undirected graphs with constant congestion
- Multiplying matrices faster than coppersmith-winograd
- Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
- Approaching Optimality for Solving SDD Linear Systems
- 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
- Structured recursive separator decompositions for planar graphs in linear time
- A new approach to computing maximum flows using electrical flows
- Approximate Maximum Flow on Separable Undirected Graphs
- Graph Sparsification by Effective Resistances
This page was built for publication:
