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)

• The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
• A queueing network-based distributed Laplacian solver for directed graphs
• Properly-weighted graph Laplacian for semi-supervised learning
• A stochastic process on a network with connections to Laplacian systems of equations
• On approximating tree spanners that are breadth first search trees
• A General Framework for Graph Sparsification
• 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
• Random walks and diffusion on networks
• iSIRA: integrated shift-invert residual Arnoldi method for graph Laplacian matrices from big data
• The resistance perturbation distance: a metric for the analysis of dynamic networks
• Semi-supervised orthogonal discriminant analysis via label propagation
• A randomized algorithm for approximating the log determinant of a symmetric positive definite matrix
• Solving Local Linear Systems with Boundary Conditions Using Heat Kernel Pagerank
• Efficient approximate solution of sparse linear systems
• Sobolev extension by linear operators
• Latent semantic analysis and Fiedler retrieval
• Nonobtuse triangulations of PSLGs
• Title not available (Why is that?)
• 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
• Reducing parallel communication in algebraic multigrid through sparsification
• 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
• Ranking and Sparsifying a Connection Graph
• 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
• The game theoreticp-Laplacian and semi-supervised learning with few labels
• Hearing the clusters of a graph: A distributed algorithm
• Multi-way spectral partitioning and higher-order cheeger inequalities
• Title not available (Why is that?)
• Matrix-Free Convex Optimization Modeling
• An Adaptive Fast Solver for a General Class of Positive Definite Matrices Via Energy Decomposition
• 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
• Global Registration of Multiple Point Clouds Using Semidefinite Programming
• Local Flow Partitioning for Faster Edge Connectivity
• Mean field analysis of personalized PageRank with implications for local graph clustering
• Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
• Persistent Laplacians: Properties, Algorithms and Implications
• A New Approach to Laplacian Solvers and Flow Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
• Title not available (Why is that?)
• Adaptive edge weighting for graph-based learning algorithms
• Graph clustering
• Duality and nonlinear graph Laplacians
• Spectral sparsification in the semi-streaming setting
• Local algorithms for sparse spanning graphs
• Solving Graph Laplacian Systems Through Recursive Partitioning and Two-Grid Preconditioning
• Accelerated multigrid for graph Laplacian operators
• Title not available (Why is that?)
• A queueing network-based distributed Laplacian solver
• 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
• Constructing near spanning trees with few local inspections
• Approximate \(\ell_0\)-penalized estimation of piecewise-constant signals on graphs
• Demand-aware network designs of bounded degree
• Learning-augmented maximum flow
• A survey on exact algorithms for the maximum flow and minimum‐cost flow problems
• Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space
• Title not available (Why is that?)
• Title not available (Why is that?)
• Metric Embedding via Shortest Path Decompositions
• Minimum cost flow in the CONGEST model
• Using Petal-Decompositions to Build a Low Stretch Spanning Tree
• Sparsification of Binary CSPs
• Sparsification of Binary CSPs
• Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions
• Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method
• Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Dirichlet Eigenvalues, Local Random Walks, and Analyzing Clusters in Graphs
• Hardness of graph-structured algebraic and symbolic problems
• RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems
• Compressive Sensing for Cut Improvement and Local Clustering
• Fitting a graph to one-dimensional data
• Brief Announcement: Minimum Cost Maximum Flow in the CONGEST Model
• Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique
• Can we locally compute sparse connected subgraphs?
• Graph curvature and local discrepancy
• Maximum length-constrained flows and disjoint paths: distributed, deterministic, and fast
• A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
• The Impact of Network Flows on Community Formation in Models of Opinion Dynamics
• Unit Capacity Maxflow in Almost $m^{4/3}$ Time
• Parametric Computation of Minimum-Cost Flows with Piecewise Quadratic Costs
• Sparsification of Two-Variable Valued Constraint Satisfaction Problems

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)