Cover Image

A Survey on the Densest Subgraph Problem and Its Variants

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Lanciano, Tommaso, Miyauchi, Atsushi, Fazzone, Adriano, Bonchi, Francesco
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms Artificial Intelligence
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Weighted Reservoir Sampling With Replacement from Data Streams
by: Meligrana, Adriano, et al.
Published: (2024)

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

Local Centrality Minimization with Quality Guarantees
by: Miyauchi, Atsushi, et al.
Published: (2024)

Multilayer Correlation Clustering
by: Miyauchi, Atsushi, et al.
Published: (2024)

Query-Efficient Correlation Clustering with Noisy Oracle
by: Kuroki, Yuko, et al.
Published: (2024)

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

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

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

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

New Parallel and Streaming Algorithms for Directed Densest Subgraph
by: Mitrović, Slobodan, et al.
Published: (2025)

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

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

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

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

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

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

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

A Faster Branching Algorithm for the Maximum $k$-Defective Clique Problem
by: Luo, Chunyu, et al.
Published: (2024)

Forbidden Subgraph Problems with Predictions
by: Böckenhauer, Hans-Joachim, et al.
Published: (2025)

Queueing, Predictions, and LLMs: Challenges and Open Problems
by: Mitzenmacher, Michael, et al.
Published: (2025)

Enhanced Methods for the Weight Constrained Shortest Path Problem
by: Ahmadi, Saman, et al.
Published: (2022)

Fast Stochastic Greedy Algorithm for $k$-Submodular Cover Problem
by: Nguyen, Hue T., et al.
Published: (2025)

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

Multi-armed Bandit and Backbone boost Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problems
by: Wang, Long, et al.
Published: (2025)

An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
by: Spaeh, Fabian, 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)

BEACON: A Benchmark for Efficient and Accurate Counting of Subgraphs
by: Najafi, Mohammad Matin, et al.
Published: (2025)

Hyper-distance Oracles in Hypergraphs
by: Preti, Giulia, et al.
Published: (2023)

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

A Mixed-Integer Conic Program for the Moving-Target Traveling Salesman Problem based on a Graph of Convex Sets
by: Philip, Allen George, et al.
Published: (2024)

A Branch-and-Bound Approach for Maximum Low-Diameter Dense Subgraph Problems
by: Zhou, Yi, et al.
Published: (2025)

A Survey on Algorithmic Developments in Optimal Transport Problem with Applications
by: Moradi, Sina
Published: (2025)

A canonical generalization of OBDD
by: Capelli, Florent, et al.
Published: (2026)

A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates
by: Weiss, Eyal, et al.
Published: (2022)

Learning-Based Algorithms for Graph Searching Problems
by: DePavia, Adela Frances, et al.
Published: (2024)

Knapsack: Connectedness, Path, and Shortest-Path
by: Dey, Palash, et al.
Published: (2023)

Identification for Tree-shaped Structural Causal Models in Polynomial Time
by: Gupta, Aaryan, et al.
Published: (2023)

Approximating Optimal Labelings for Temporal Connectivity
by: Carnevale, Daniele, et al.
Published: (2025)