Dense subgraphs in random graphs

DOI10.1016/j.dam.2019.01.032zbMath1409.05180arXiv1803.10349OpenAlexW2964060733MaRDI QIDQ1741497

Alexander Veremyev, Julian Sahasrabudhe, Béla Bollobás, Paul N. Balister

Publication date: 3 May 2019

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

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

zbMATH Keywords

random graphscliquesbinomial random graphprobabilistic combinatoricsErdős-Renyi random graphdense clustersnetworks in sociometry

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Density (toughness, etc.) (05C42)

Related Items (4)

Sparse high-dimensional linear regression. Estimating squared error and a phase transition ⋮ An opposition-based memetic algorithm for the maximum quasi-clique problem ⋮ Testing correlation of unlabeled random graphs ⋮ Asymptotic bounds for clustering problems in random graphs

Uses Software

• MCODE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs
• Statistical analysis of financial networks
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Multivariate algorithmics for finding cohesive subnetworks
• Micro-review synthesis for multi-entity summarization
• On the maximum quasi-clique problem
• On clique relaxation models in network analysis
• The complexity of detecting fixed-density clusters
• Largest sparse subgraphs of random graphs
• The t-Improper Chromatic Number of Random Graphs
• On colouring random graphs
• Cliques in random graphs
• Paths in graphs
• Reducibility among Combinatorial Problems
• Some remarks on the theory of graphs

This page was built for publication: Dense subgraphs in random graphs