3 papers
cs.DS2025
New Parallel and Streaming Algorithms for Directed Densest Subgraph
Slobodan Mitrović, Theodore Pan, Mahdi Qaempanah +1
Finding dense subgraphs is a fundamental problem with applications to community detection, clustering, and data mining. Our work focuses on finding approximate densest subgraphs in…
cs.DS2025
Breaking the Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
Anders Aamand, Justin Y. Chen, Mina Dalirrooyfard +4
We study differentially private algorithms for graph cut sparsification, a fundamental problem in algorithms, privacy, and machine learning. While significant progress has been mad…
cs.DS2025
SPARSE-PIVOT: Dynamic correlation clustering for node insertions
Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović
We present a new Correlation Clustering algorithm for a dynamic setting where nodes are added one at a time. In this model, proposed by Cohen-Addad, Lattanzi, Maggiori, and Parotsi…