The densest subgraph problem in sparse random graphs

DOI10.1214/14-AAP1091zbMath1336.60010arXiv1312.4494OpenAlexW1555111922MaRDI QIDQ259578

Justin Salez, Venkat Anantharam

Publication date: 11 March 2016

Published in: The Annals of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

unimodularityload balancinglocal weak convergencemaximum subgraph densityobjective methodpairing model

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Stochastic network models in operations research (90B15) Combinatorial probability (60C05)

Related Items (4)

Load balancing in hypergraphs ⋮ Sparse expanders have negative curvature ⋮ Matching recovery threshold for correlated random graphs ⋮ Topological price of anarchy bounds for clustering games on networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matchings on infinite graphs
• Belief propagation for optimal edge cover in the random complete graph
• A survey of max-type recursive distributional equations
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Recurrence of distributional limits of finite planar graphs
• Balanced loads in infinite networks
• Processes on unimodular random networks
• The ?(2) limit in the random assignment problem
• Critical behavior in inhomogeneous random graphs
• Weighted enumeration of spanning subgraphs in locally tree-like graphs
• Load balancing and orientability thresholds for random hypergraphs
• Belief Propagation: An Asymptotically Optimal Algorithm for the Random Assignment Problem
• Performance of global load balancing by local adjustment
• Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
• The Probability That a Random Multigraph is Simple
• The Multiple-orientability Thresholds for Random Hypergraphs
• Asymptotic Enumeration of Spanning Trees

This page was built for publication: The densest subgraph problem in sparse random graphs