Computing the \(k\) densest subgraphs of a graph

DOI10.1016/j.ipl.2022.106316OpenAlexW3005673592MaRDI QIDQ2094387

Danny Hermelin, Riccardo Dondi

Publication date: 28 October 2022

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

algorithmsdensest subgraphalgorithm designalgorithmic aspects of networksnetwork mining and analysis

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Complexity of finding dense subgraphs
• Multivariate algorithmics for finding cohesive subnetworks
• Top-\(k\) overlapping densest subgraphs
• The densest subgraph problem with a convex/concave size function
• Top-\(k\) overlapping densest subgraphs: approximation algorithms and computational complexity
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• Finding Dense Subgraphs with Size Bounds
• On Finding Dense Subgraphs
• A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory
• Generating Sparse 2-Spanners
• A Fast Parametric Maximum Flow Algorithm and Applications
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Reducibility among Combinatorial Problems
• Greedily finding a dense subgraph
• Max flows in O(nm) time, or better
• The dense \(k\)-subgraph problem

This page was built for publication: Computing the \(k\) densest subgraphs of a graph