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

DOI10.1145/1007352.1007372zbMATH Open1192.65048OpenAlexW2045107949MaRDI QIDQ3580949FDOQ3580949

Authors: Daniel A. Spielman, Shang-Hua Teng 

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

Recommendations

• A linear time algorithm for graph partition problems
• Graph partitioning using linear and semidefinite programming
• scientific article; zbMATH DE number 4062622
• Towards an SDP-based approach to spectral methods: a nearly-linear-time algorithm for graph partitioning and decomposition
• Linear time algorithms for finding sparsest cuts in various graph classes
• Approximation Algorithms for Some Graph Partitioning Problems
• A linear time algorithm for determining almost bipartite graphs
• Linear and quadratic programming approaches for the general graph partitioning problem
• Partitioning into degenerate graphs in linear time
• Linear time optimization algorithms for \(P_ 4\)-sparse graphs

Mathematics Subject Classification ID

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

Cited In (only showing first 100 items - show all)

• A queueing network-based distributed Laplacian solver for directed graphs
• Properly-weighted graph Laplacian for semi-supervised learning
• An adaptive fast solver for a general class of positive definite matrices via energy decomposition
• Persistent Laplacians: properties, algorithms and implications
• A stochastic process on a network with connections to Laplacian systems of equations
• Bayesian model selection with graph structured sparsity
• On approximating tree spanners that are breadth first search trees
• Local flow partitioning for faster edge connectivity
• Constructing linear-sized spectral sparsification in almost-linear time
• Random walks and local cuts in graphs
• Engineering a combinatorial Laplacian solver: lessons learned
• Sparse Matrix Factorizations for Fast Linear Solvers with Application to Laplacian Systems
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Sparse reliable graph backbones
• A general framework for graph sparsification
• Solving graph Laplacian systems through recursive partitioning and two-grid preconditioning
• Random walks and diffusion on networks
• A new approach to Laplacian solvers and flow problems
• iSIRA: integrated shift-invert residual Arnoldi method for graph Laplacian matrices from big data
• Ranking and sparsifying a connection graph
• The resistance perturbation distance: a metric for the analysis of dynamic networks
• Sparsified Cholesky and multigrid solvers for connection Laplacians
• Semi-supervised orthogonal discriminant analysis via label propagation
• A randomized algorithm for approximating the log determinant of a symmetric positive definite matrix
• Matrix-free convex optimization modeling
• Efficient approximate solution of sparse linear systems
• Sobolev extension by linear operators
• On multiplicative \(\lambda\)-approximations and some geometric applications
• Latent semantic analysis and Fiedler retrieval
• Nonobtuse triangulations of PSLGs
• Spectral sparsification of graphs
• From graph cuts to isoperimetric inequalities: convergence rates of Cheeger cuts on data clouds
• Improved spectral sparsification and numerical algorithms for SDD matrices
• Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
• A linear work, \(O(n^{1/6})\) time, parallel algorithm for solving planar Laplacians
• Approaching optimality for solving SDD linear systems
• Tree spanners of bounded degree graphs
• Contrast invariant SNR and isotonic regressions
• Iteratively reweighted least squares and slime mold dynamics: connection and convergence
• A linear time algorithm for graph partition problems
• Advances in metric embedding theory
• The approximate duality gap technique: a unified theory of first-order methods
• Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
• A Nonlinear Algebraic Multigrid Framework for the Power Flow Equations
• A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
• The Small Community Phenomenon in Networks: Models, Algorithms and Applications
• Hearing the clusters of a graph: A distributed algorithm
• Title not available (Why is that?)
• A Simple Efficient Interior Point Method for Min-Cost Flow
• Communities, Random Walks, and Social Sybil Defense
• Reconstructing Markov processes from independent and anonymous experiments
• Computing heat kernel PageRank and a local clustering algorithm
• Mean field analysis of personalized PageRank with implications for local graph clustering
• Solving local linear systems with boundary conditions using heat kernel pagerank
• Faster spectral sparsification and numerical algorithms for SDD matrices
• Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
• Learning by unsupervised nonlinear diffusion
• Adaptive edge weighting for graph-based learning algorithms
• Graph clustering
• Duality and nonlinear graph Laplacians
• Spectral sparsification in the semi-streaming setting
• Multi-way spectral partitioning and higher-order Cheeger inequalities
• Accelerated multigrid for graph Laplacian operators
• Title not available (Why is that?)
• A queueing network-based distributed Laplacian solver
• Global registration of multiple point clouds using semidefinite programming
• Modified Cheeger and ratio cut methods using the Ginzburg–Landau functional for classification of high-dimensional data
• A combinatorial cut-toggling algorithm for solving Laplacian linear systems
• Approximate \(\ell_0\)-penalized estimation of piecewise-constant signals on graphs
• Demand-aware network designs of bounded degree
• The game theoretic \(p\)-Laplacian and semi-supervised learning with few labels
• Hardness results for structured linear systems
• Learning-augmented maximum flow
• A survey on exact algorithms for the maximum flow and minimum‐cost flow problems
• Title not available (Why is that?)
• Metric Embedding via Shortest Path Decompositions
• The impact of network flows on community formation in models of opinion dynamics
• Dirichlet eigenvalues, local random walks, and analyzing clusters in graphs
• Minimum cost flow in the CONGEST model
• Sparsification of Binary CSPs
• Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions
• Parametric computation of minimum-cost flows with piecewise quadratic costs
• Sparsification of two-variable valued constraint satisfaction problems
• Using petal-decompositions to build a low stretch spanning tree
• Title not available (Why is that?)
• Hardness of graph-structured algebraic and symbolic problems
• Reducing parallel communication in algebraic multigrid through sparsification
• Online row sampling
• Perron-Frobenius theory in nearly linear time: positive eigenvectors, M-matrices, graph kernels, and other applications
• Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
• RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems
• Fitting a graph to one-dimensional data
• Sparsification of binary CSPs
• Brief Announcement: Minimum Cost Maximum Flow in the CONGEST Model
• Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique
• Accelerated extra-gradient descent: a novel accelerated first-order method
• Local algorithms for bounded degree sparsifiers in sparse graphs
• Can we locally compute sparse connected subgraphs?
• Graph curvature and local discrepancy
• Maximum length-constrained flows and disjoint paths: distributed, deterministic, and fast

This page was built for publication: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3580949)