In search of the densest subgraph
type: Item
instance of: scholarly article
title: In search of the densest subgraph
zbMATH Open document ID: 1461.05210
author: Zohre R. Mojaveri
author: Andras Farago
published in: Algorithms
publication date: 2020-10-08T00:00:00Z
review text: Summary: In this survey paper, we review various concepts of graph density, as well as associated theorems and algorithms. Our goal is motivated by the fact that, in many applications, it is a key algorithmic task to extract a densest subgraph from an input graph, according to some appropriate definition of graph density. While this problem has been the subject of active research for over half of a century, with many proposed variants and solutions, new results still continuously emerge in the literature. This shows both the importance and the richness of the subject. We also identify some interesting open problems in the field.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C82
zbMATH DE Number: 7257777
zbMATH Keywords: dense subgraph
zbMATH Keywords: algorithms
zbMATH Keywords: graph density
zbMATH Keywords: clusters in graphs
zbMATH Keywords: big data
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a12080157
OpenAlex ID: W2964670465
cites work: A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory
cites work: A Fast Parametric Maximum Flow Algorithm and Applications
cites work: Q2753729
cites work: Determination of the densest subgraph
cites work: A general tractable density concept for graphs
cites work: k-Degenerate Graphs
cites work: Smallest-last ordering and clustering and graph coloring algorithms
cites work: The densest subgraph problem with a convex/concave size function
cites work: Algorithms for the Densest Subgraph with at Least k Vertices and with a Specified Subset
cites work: Algorithmic Aspects of Graph Connectivity
cites work: Q5592932
cites work: Q4198056
cites work: Network Analysis
cites work: Algorithms for maximum independent sets
cites work: Approximating maximum independent sets by excluding subgraphs
cites work: Approximating Maximum Clique by Removing Subgraphs
cites work: Q3002782
cites work: A New Algorithm for Generating All the Maximal Independent Sets
cites work: On generating all maximal independent sets
cites work: Complexity of finding dense subgraphs
cites work: Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
cites work: Densest k-Subgraph Approximation on Intersection Graphs
cites work: Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
cites work: Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
cites work: Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
cites work: Extensions of Turán's theorem on graphs
cites work: On the structure of linear graphs
cites work: Q3330973
cites work: Forests, frames, and games: Algorithms for matroid sums and applications
cites work: On chromatic number of graphs and set-systems
cites work: Random graphs.
cites work: On colouring random graphs
Wikidata QID: Q127409266
DOI: 10.3390/A12080157
description: scientific article; zbMATH DE number 7257777