Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems

DOI10.1145/1007352.1007372zbMath1192.65048OpenAlexW2045107949MaRDI QIDQ3580949

Publication date: 15 August 2010

Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1007352.1007372

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Linear equations (linear algebraic aspects) (15A06)

Related Items

On approximating tree spanners that are breadth first search trees ⋮ Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Adaptive edge weighting for graph-based learning algorithms ⋮ Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ iSIRA: integrated shift-invert residual Arnoldi method for graph Laplacian matrices from big data ⋮ The Small Community Phenomenon in Networks: Models, Algorithms and Applications ⋮ From graph cuts to isoperimetric inequalities: convergence rates of Cheeger cuts on data clouds ⋮ Nonobtuse triangulations of PSLGs ⋮ Iteratively reweighted least squares and slime mold dynamics: connection and convergence ⋮ Unnamed Item ⋮ A stochastic process on a network with connections to Laplacian systems of equations ⋮ Unit Capacity Maxflow in Almost $m^{4/3}$ Time ⋮ Metric Embedding via Shortest Path Decompositions ⋮ Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time ⋮ Parametric Computation of Minimum-Cost Flows with Piecewise Quadratic Costs ⋮ Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness ⋮ Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method ⋮ Unnamed Item ⋮ Can we locally compute sparse connected subgraphs? ⋮ Latent semantic analysis and Fiedler retrieval ⋮ A randomized algorithm for approximating the log determinant of a symmetric positive definite matrix ⋮ Random walks and local cuts in graphs ⋮ Spectral sparsification in the semi-streaming setting ⋮ Fitting a graph to one-dimensional data ⋮ Persistent Laplacians: Properties, Algorithms and Implications ⋮ Dirichlet Eigenvalues, Local Random Walks, and Analyzing Clusters in Graphs ⋮ A Simple Efficient Interior Point Method for Min-Cost Flow ⋮ Computing heat kernel PageRank and a local clustering algorithm ⋮ Sparsification of Binary CSPs ⋮ Unnamed Item ⋮ Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space ⋮ Modified Cheeger and ratio cut methods using the Ginzburg–Landau functional for classification of high-dimensional data ⋮ Solving Graph Laplacian Systems Through Recursive Partitioning and Two-Grid Preconditioning ⋮ Random walks and diffusion on networks ⋮ Demand-aware network designs of bounded degree ⋮ A combinatorial cut-toggling algorithm for solving Laplacian linear systems ⋮ Matrix-Free Convex Optimization Modeling ⋮ Contrast invariant SNR and isotonic regressions ⋮ The resistance perturbation distance: a metric for the analysis of dynamic networks ⋮ Tree spanners of bounded degree graphs ⋮ Unnamed Item ⋮ Norms of structured random matrices ⋮ Duality and nonlinear graph Laplacians ⋮ A survey on exact algorithms for the maximum flow and minimum‐cost flow problems ⋮ Minimum cost flow in the CONGEST model ⋮ Sparse reliable graph backbones ⋮ Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Hardness of graph-structured algebraic and symbolic problems ⋮ Brief Announcement: Minimum Cost Maximum Flow in the CONGEST Model ⋮ Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique ⋮ Reconstructing Markov processes from independent and anonymous experiments ⋮ Hearing the clusters of a graph: A distributed algorithm ⋮ Constructing near spanning trees with few local inspections ⋮ Graph clustering ⋮ Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs ⋮ A queueing network-based distributed Laplacian solver for directed graphs ⋮ The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods ⋮ Using Petal-Decompositions to Build a Low Stretch Spanning Tree ⋮ Advances in metric embedding theory ⋮ Engineering a combinatorial Laplacian solver: lessons learned ⋮ A queueing network-based distributed Laplacian solver ⋮ Accelerated multigrid for graph Laplacian operators ⋮ An Adaptive Fast Solver for a General Class of Positive Definite Matrices Via Energy Decomposition ⋮ The game theoreticp-Laplacian and semi-supervised learning with few labels ⋮ Approximate $\ell_0$-penalized estimation of piecewise-constant signals on graphs ⋮ Mean field analysis of personalized PageRank with implications for local graph clustering ⋮ Multi-way spectral partitioning and higher-order cheeger inequalities ⋮ Ranking and Sparsifying a Connection Graph ⋮ A Nonlinear Algebraic Multigrid Framework for the Power Flow Equations ⋮ Semi-supervised orthogonal discriminant analysis via label propagation ⋮ Properly-weighted graph Laplacian for semi-supervised learning ⋮ Local Flow Partitioning for Faster Edge Connectivity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Local algorithms for sparse spanning graphs ⋮ Sparsification of Binary CSPs ⋮ Reducing Parallel Communication in Algebraic Multigrid through Sparsification ⋮ A General Framework for Graph Sparsification ⋮ Communities, Random Walks, and Social Sybil Defense ⋮ A New Approach to Laplacian Solvers and Flow Problems ⋮ Solving Local Linear Systems with Boundary Conditions Using Heat Kernel Pagerank ⋮ Global Registration of Multiple Point Clouds Using Semidefinite Programming ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Sobolev extension by linear operators ⋮ RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems ⋮ The Impact of Network Flows on Community Formation in Models of Opinion Dynamics ⋮ A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix ⋮ Sparsification of Two-Variable Valued Constraint Satisfaction Problems ⋮ Sparse Matrix Factorizations for Fast Linear Solvers with Application to Laplacian Systems ⋮ Compressive Sensing for Cut Improvement and Local Clustering