Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems

2003/10/28 by Spielman, Daniel A., Teng, Shang-Hua · 15 citations
#Data Structures and Algorithms (cs.DS) #F.2.1 #FOS: Computer and information sciences #FOS: Mathematics #G.1.3 #Numerical Analysis (math.NA)

paper · doi:10.48550/arxiv.cs/0310051

Abstract

This paper has been divided into three papers. arXiv:0809.3232, arXiv:0808.4134, arXiv:cs/0607105

Cited by

• Parallel Spectral Graph Sparsification via Low Diameter Decompositions
• Sparsification of sums with respect to convex cones
• Graph-based Nearest Neighbors with Dynamic Updates via Random Walks
• Acceleration for Distributed Transshipment and Parallel Maximum Flow
• Hedgegraph Polymatroids
• Efficient Network Reconfiguration by Randomized Switching
• Generalized Flow in Nearly-linear Time on Moderately Dense Graphs
• Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
• Towards Constant Time Multi-Call Rumor Spreading on Small-Set Expanders
• On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time
• Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model
• Sparsifying Cayley Graphs on Every Group
• Spectrum Estimation through Kirchhoff Random Forests
• A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection
• Variable Min-Cut Max-Flow Bounds and Algorithms in Finite Regime

Related

• Improved Space-efficient Linear Time Algorithms for Some Classical Graph Problems
• A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning
• A nearly-mlogn time solver for SDD linear systems
• Dynamic Graph Algorithms and Graph Sparsification: New Techniques and Connections
• Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time