Cover Image

New Parallel and Streaming Algorithms for Directed Densest Subgraph

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Mitrović, Slobodan, Pan, Theodore, Qaempanah, Mahdi, Raeisi, Mohammad Amin
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models
by: Dalirrooyfard, Mina, et al.
Published: (2024)

Destroying Densest Subgraphs is Hard
by: Bazgan, Cristina, et al.
Published: (2024)

An Efficient and Exact Algorithm for Locally h-Clique Densest Subgraph Discovery
by: Xu, Xiaojia, et al.
Published: (2024)

Deterministic $(1+\varepsilon)$-Approximate Maximum Matching with $\mathsf{poly}(1/\varepsilon)$ Passes in the Semi-Streaming Model and Beyond
by: Fischer, Manuela, et al.
Published: (2021)

Scalable $k$-clique Densest Subgraph Search
by: Ye, Xiaowei, et al.
Published: (2024)

Almost Tight Bounds for Differentially Private Densest Subgraph
by: Dinitz, Michael, et al.
Published: (2023)

Fast and Simple Densest Subgraph with Predictions
by: Bui, Thai, et al.
Published: (2025)

Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates
by: Mitrović, Slobodan, et al.
Published: (2026)

A framework for boosting matching approximation: parallel, distributed, and dynamic
by: Mitrović, Slobodan, et al.
Published: (2025)

Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs
by: Łącki, Jakub, et al.
Published: (2025)

Fast and Optimal Incremental Parametric Procedure for the Densest Subgraph Problem: An Experimental Study
by: Hochbaum, Dorit S., et al.
Published: (2025)

In-depth Analysis of Densest Subgraph Discovery in a Unified Framework
by: Zhou, Yingli, et al.
Published: (2024)

Dynamic PageRank: Algorithms and Lower Bounds
by: Jayaram, Rajesh, et al.
Published: (2024)

SPARSE-PIVOT: Dynamic correlation clustering for node insertions
by: Dalirrooyfard, Mina, et al.
Published: (2025)

Locally computing edge orientations
by: Mitrović, Slobodan, et al.
Published: (2025)

A Simple Average-case Analysis of Recursive Randomized Greedy MIS
by: Dalirrooyfard, Mina, et al.
Published: (2026)

A Survey on the Densest Subgraph Problem and Its Variants
by: Lanciano, Tommaso, et al.
Published: (2023)

A Note on Approximability of Densest At-Least-k-Subgraph
by: Laekhanukit, Bundit, et al.
Published: (2026)

Multiplicative Weights Update, Area Convexity and Random Coordinate Descent for Densest Subgraph Problems
by: Nguyen, Ta Duy, et al.
Published: (2024)

Efficient Processing of Subsequent Densest Subgraph Query
by: Hung, Chia-Yang, et al.
Published: (2024)

Approximate counting of permutation patterns
by: Ben-Eliezer, Omri, et al.
Published: (2024)

The Vertex-Attribute-Constrained Densest $k$-Subgraph Problem
by: Lu, Qiheng, et al.
Published: (2025)

Tighter Bounds for Local Differentially Private Core Decomposition and Densest Subgraph
by: Henzinger, Monika, et al.
Published: (2024)

Parallel Set Cover and Hypergraph Matching via Uniform Random Sampling
by: Dhulipala, Laxman, et al.
Published: (2024)

Faster Semi-streaming Matchings via Alternating Trees
by: Mitrović, Slobodan, et al.
Published: (2024)

Differentially Private Densest Subgraph Detection
by: Nguyen, Dung, et al.
Published: (2021)

Dynamic Construction of the Lovász Local Lemma
by: Haeupler, Bernhard, et al.
Published: (2026)

Streaming and Massively Parallel Algorithms for Euclidean Max-Cut
by: Menand, Nicolas, et al.
Published: (2025)

Streaming Graph Algorithms in the Massively Parallel Computation Model
by: Czumaj, Artur, et al.
Published: (2025)

Streaming Algorithms via Local Algorithms for Maximum Directed Cut
by: Saxena, Raghuvansh R., et al.
Published: (2024)

Continual Release of Densest Subgraphs: Privacy Amplification & Sublinear Space via Subsampling
by: Zhou, Felix
Published: (2025)

New Parameterized and Exact Exponential Time Algorithms for Strongly Connected Steiner Subgraph
by: Ameli, Afrouz Jabal, et al.
Published: (2026)

Subexponential Parameterized Algorithms for Hitting Subgraphs
by: Lokshtanov, Daniel, et al.
Published: (2024)

$Δ$-Motif: Parallel Subgraph Isomorphism via Tabular Operations
by: Wang, Yulun, et al.
Published: (2025)

On Densest $k$-Subgraph Mining and Diagonal Loading: Optimization Landscape and Finite-Step Exact Convergence Analysis
by: Lu, Qiheng, et al.
Published: (2024)

OptiRefine: Densest subgraphs and maximum cuts with $k$ refinements
by: Tu, Sijing, et al.
Published: (2025)

New Algorithms and Lower Bounds for Streaming Tournaments
by: Ghosh, Prantar, et al.
Published: (2024)

Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
by: Aamand, Anders, et al.
Published: (2025)

The Densest SWAMP problem: subhypergraphs with arbitrary monotonic partial edge rewards
by: Bengali, Vedangi, et al.
Published: (2025)

Learning-Augmented Streaming Algorithms for Approximating MAX-CUT
by: Dong, Yinhao, et al.
Published: (2024)