Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
Publication:487267
DOI10.1007/s00224-013-9444-5zbMath1314.68361arXiv1111.1750OpenAlexW1991838331MaRDI QIDQ487267
Kanat Tangwongsan, Anupam Gupta, Richard Peng, Guy E. Blelloch, Ioannis Koutis, Gary Lee Miller
Publication date: 19 January 2015
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1111.1750
linear systemsparallel algorithmslow-diameter decompositionlow-stretch spanning treeslow-stretch subgraphs
Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Linear equations (linear algebraic aspects) (15A06)
Related Items (9)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The tail of the hypergeometric distribution
- A Mathematical View of Interior-Point Methods in Convex Optimization
- Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
- High-Probability Parallel Transitive-Closure Algorithms
- The Laplacian Paradigm: Emerging Algorithms for Massive Graphs
- Lower-stretch spanning trees
- Complexity of network synchronization
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- Fast and Efficient Parallel Solution of Sparse Linear Systems
- A Graph-Theoretic Game and Its Application to the k-Server Problem
- A Randomized Parallel Algorithm for Single-Source Shortest Paths
- Polylog-time and near-linear work approximation scheme for undirected shortest paths
- Probability Inequalities for Sums of Bounded Random Variables
- Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
- A Nearly-m log n Time Solver for SDD Linear Systems
This page was built for publication: Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs