Sandwiching a densest subgraph by consecutive cores

DOI10.1002/RSA.20543MaRDI QIDQ3192385zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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)