Finding Dense Subgraphs with Size Bounds

DOI10.1007/978-3-540-95995-3_3zbMath1207.05191OpenAlexW1888358353MaRDI QIDQ3601165

Reid Andersen, Kumar Chellapilla

Publication date: 10 February 2009

Published in: Algorithms and Models for the Web-Graph (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-95995-3_3

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Internet topics (68M11) Density (toughness, etc.) (05C42)

Related Items

Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis, Algorithms for the Densest Subgraph with at Least k Vertices and with a Specified Subset, Test dense subgraphs in sparse uniform hypergraph, Finding connected \(k\)-subgraphs with high density, Finding dense subgraphs with maximum weighted triangle density, Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem, Finding Connected Dense $$k$$-Subgraphs, In search of dense subgraphs: How good is greedy peeling?, Covering a graph with densest subgraphs, On size-constrained minimum \(s\mathrm{-}t\) cut problems and size-constrained dense subgraph problems, Parameterized complexity of finding small degree-constrained subgraphs, An Escape Time Formulation for Subgraph Detection and Partitioning of Directed Graphs, Discovering subjectively interesting multigraph patterns, Sparse Graphs Are Near-Bipartite, Exact algorithms for problems related to the densest \(k\)-set problem, On set expansion problems and the small set expansion conjecture, Finding densest \(k\)-connected subgraphs, Top-\(k\) overlapping densest subgraphs, Top-\(k\) overlapping densest subgraphs: approximation algorithms and computational complexity, Homophily outlier detection in non-IID categorical data, Threshold-based preprocessing for approximating the weighted dense \(k\)-subgraph problem, The densest subgraph problem with a convex/concave size function, Proportionally dense subgraph of maximum size: complexity and approximation, Computing the \(k\) densest subgraphs of a graph, On solving the densestk-subgraph problem on large graphs