The densest subgraph problem in sparse random graphs
From MaRDI portal
Publication:259578
DOI10.1214/14-AAP1091zbMath1336.60010arXiv1312.4494MaRDI 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
unimodularityload balancinglocal weak convergencemaximum subgraph densityobjective methodpairing model
05C80: Random graphs (graph-theoretic aspects)
90B15: Stochastic network models in operations research
60C05: Combinatorial probability
Related Items
Matching recovery threshold for correlated random graphs, Topological price of anarchy bounds for clustering games on networks, Load balancing in hypergraphs, Sparse expanders have negative curvature
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
