A distributed algorithm for spectral sparsification of graphs with applications to data clustering

DOI10.1007/978-3-030-63072-0_31zbMath1483.68259arXiv2003.10612OpenAlexW3013824734MaRDI QIDQ2056927

Fabricio Mendoza-Granada, Marcos Villagra

Publication date: 8 December 2021

Full work available at URL: https://arxiv.org/abs/2003.10612

zbMATH Keywords

distributed algorithmscommunication complexitydata clusteringspectral sparsificationdense graphs

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Distributed algorithms (68W15) Density (toughness, etc.) (05C42) Communication complexity, information complexity (68Q11)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Spectral Sparsification of Graphs
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time
• Communication Complexity
• Twice-ramanujan sparsifiers
• Multi-way spectral partitioning and higher-order cheeger inequalities

This page was built for publication: A distributed algorithm for spectral sparsification of graphs with applications to data clustering