Sandwiching a densest subgraph by consecutive cores

DOI10.1002/RSA.20543zbMATH Open1322.05085OpenAlexW2056191455MaRDI QIDQ3192385FDOQ3192385

Authors: Pu Gao 

Publication date: 12 October 2015

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20543

Recommendations

• In search of the densest subgraph
• On Finding Dense Subgraphs
• Covering a graph with densest subgraphs
• Finding densest \(k\)-connected subgraphs
• Finding dense subgraphs
• Determination of the densest subgraph
• Greedily Finding a Dense Subgraph
• Greedily finding a dense subgraph
• Finding Dense Subgraphs with Size Bounds
• The dense \(k\)-subgraph problem

zbMATH Keywords

densest subgraph\(k\)-corebalanced \(k\)-core thresholddensest core

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42)

Cites Work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Sudden emergence of a giant \(k\)-core in a random graph
• Load balancing and orientability thresholds for random hypergraphs
• Performance of global load balancing by local adjustment
• Asymptotic enumeration of sparse graphs with a minimum degree constraint
• Cores in random hypergraphs and Boolean formulas
• Encores on cores
• Almost all graphs with 1.44n edges are 3-colorable
• On the threshold for \(k\)-regular subgraphs of random graphs

This page was built for publication: Sandwiching a densest subgraph by consecutive cores

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3192385)