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