A general framework for graph sparsification
From MaRDI portal
Publication:5419076
DOI10.1145/1993636.1993647zbMath1288.68118arXiv1004.4080OpenAlexW2019040312MaRDI QIDQ5419076
Nicholas J. A. Harvey, Ramesh Hariharan, Debmalya Panigrahi, Wai Shing Fung
Publication date: 5 June 2014
Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1004.4080
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40) Signed and weighted graphs (05C22) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
Diffusion centrality: a paradigm to maximize spread in social networks, Minimum Cuts and Sparsification in Hypergraphs, Sparsification of Binary CSPs, Communication-efficient distributed graph clustering and sparsification under duplication models, The algebraic structure of the densification and the sparsification tasks for CSPs, Better hardness results for the minimum spanning tree congestion problem, Determinant-Preserving Sparsification of SDDM Matrices, Faster cut sparsification of weighted graphs, Activity preserving graph simplification, Sparsification of Binary CSPs, Spanning tree constrained determinantal point processes are hard to (approximately) evaluate, Reducing Parallel Communication in Algebraic Multigrid through Sparsification, A General Framework for Graph Sparsification, Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs, Tree-Based Coarsening and Partitioning of Complex Networks, Sparsification of Two-Variable Valued Constraint Satisfaction Problems, A fast algorithm for manifold learning by posing it as a symmetric diagonally dominant linear system
