Complexity of finding dense subgraphs

DOI10.1016/S0166-218X(01)00243-8zbMath1002.68108MaRDI QIDQ1613384

Yuichi Asahiro, Kazuo Iwama, Refael Hassin

Publication date: 29 August 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

regular graphdense subgraph problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs ⋮ Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis ⋮ Complexity and approximability of the happy set problem ⋮ The inverse protein folding problem on 2D and 3D lattices ⋮ Finding dense subgraphs with maximum weighted triangle density ⋮ Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem ⋮ Dense neighborhoods on affinity graph ⋮ Covering a graph with densest subgraphs ⋮ Graph clustering ⋮ A dynamic edge covering and scheduling problem: complexity results and approximation algorithms ⋮ Better lower and upper bounds for the minimum rainbow subgraph problem ⋮ Parameterized algorithms for the happy set problem ⋮ A polyhedral study of the maximum edge subgraph problem ⋮ In search of the densest subgraph ⋮ Unnamed Item ⋮ Approximation algorithms for the minimum rainbow subgraph problem ⋮ Upper bounds and exact algorithms for \(p\)-dispersion problems ⋮ Graph classes and approximability of the happy set problem ⋮ The complexity of detecting fixed-density clusters ⋮ Top-\(k\) overlapping densest subgraphs: approximation algorithms and computational complexity ⋮ Minimum budget for misinformation blocking in online social networks ⋮ A polyhedral study of the maximum edge subgraph problem ⋮ Graphs without a partition into two proportionally dense subgraphs ⋮ Sequential Monte Carlo for maximum weight subgraphs with application to solving image jigsaw puzzles ⋮ On the Complexity of Robust PCA and ℓ₁-Norm Low-Rank Matrix Approximation ⋮ Combinatorial properties and further facets of maximum edge subgraph polytopes ⋮ Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem ⋮ Proportionally dense subgraph of maximum size: complexity and approximation ⋮ Computing the \(k\) densest subgraphs of a graph

Cites Work

• Some simplified NP-complete graph problems
• Approximation algorithms for maximum dispersion
• Heuristic and Special Case Algorithms for Dispersion Problems
• A Fast Parametric Maximum Flow Algorithm and Applications
• Greedily Finding a Dense Subgraph
• Reducibility among Combinatorial Problems
• The complexity of theorem-proving procedures
• Maximum dispersion problem in dense graphs
• The dense \(k\)-subgraph problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item