Density Independent Algorithms for Sparsifying k-Step Random Walks
From MaRDI portal
Publication:5002617
DOI10.4230/LIPIcs.APPROX-RANDOM.2017.14zbMath1467.05255arXiv1702.06110OpenAlexW2591750614MaRDI QIDQ5002617
Pavel Kolev, Gorav Jindal, Richard Peng, Saurabh Sawlani
Publication date: 28 July 2021
Full work available at URL: https://arxiv.org/abs/1702.06110
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Random walks on graphs (05C81)
Related Items (2)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Faster spectral sparsification and numerical algorithms for SDD matrices
- Colorful triangle counting and a \textsc{MapReduce} implementation
- User-friendly tail bounds for sums of random matrices
- Spectral sparsification via random spanners
- Efficient Sampling Methods for Discrete Distributions
- Uniform Sampling for Matrix Approximation
- Fast Algorithms for Finding Nearest Common Ancestors
- Input Sparsity Time Low-rank Approximation via Ridge Leverage Score Sampling
- A Framework for Analyzing Resparsification Algorithms
- Sampling random spanning trees faster than matrix multiplication
- Listing Triangles
- Shortest-path queries in static networks
- Fibonacci heaps and their uses in improved network optimization algorithms
- An efficient parallel solver for SDD linear systems
- Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
- Sparsified Cholesky and multigrid solvers for connection laplacians
- Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
- Using petal-decompositions to build a low stretch spanning tree
- Graph Sparsification by Effective Resistances
This page was built for publication: Density Independent Algorithms for Sparsifying k-Step Random Walks
