Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
From MaRDI portal
Publication:3376664
DOI10.1002/rsa.20072zbMath1094.05050arXivmath/0309441OpenAlexW2963332076MaRDI QIDQ3376664
Tomasz Nowicki, David Gamarnik, Grzegorz Świrszcz
Publication date: 24 March 2006
Published in: Random Structures and Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0309441
Related Items (18)
On independent sets in random graphs ⋮ Limits of discrete distributions and Gibbs measures on random graphs ⋮ Large deviations of the greedy independent set algorithm on sparse random graphs ⋮ SERVER WAITING TIMES IN INFINITE SUPPLY POLLING SYSTEMS WITH PREPARATION TIMES ⋮ Analysis of an iterated local search algorithm for vertex cover in sparse random graphs ⋮ Dismantling Sparse Random Graphs ⋮ Replica symmetry of the minimum matching ⋮ First-passage percolation on a ladder graph, and the path cost in a VCG auction ⋮ Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections ⋮ Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs ⋮ On maximal hard-core thinnings of stationary particle processes ⋮ Endogeny for the logistic recursive distributional equation ⋮ Combinatorial approach to the interpolation method and scaling limits in sparse random graphs ⋮ Sparse graphs: Metrics and random models ⋮ Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models ⋮ The planted matching problem: phase transitions and exact results ⋮ Weighted enumeration of spanning subgraphs in locally tree-like graphs ⋮ The densest subgraph problem in sparse random graphs
Cites Work
This page was built for publication: Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
