89 citations · 243 across the 15 of their papers we have counts for
Showing 2008Show all
3 papers · 1 filter
cond-mat.stat-mech2008★ 51 cited
Statistical Mechanics of Steiner trees
M. Bayati, C. Borgs, A. Braunstein +3
The Minimum Weight Steiner Tree (MST) is an important combinatorial optimization problem over networks that has applications in a wide range of fields. Here we discuss a general te…
cond-mat.stat-mech2008★ 48 cited
On the exactness of the cavity method for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs
M. Bayati, C. Borgs, J. Chayes +1
We consider the general problem of finding the minimum weight b-matching on arbitrary graphs. We prove that, whenever the linear programming relaxation of the problem has no fracti…
math.CO2008★ 4 cited
Moments of Two-Variable Functions and the Uniqueness of Graph Limits
Christian Borgs, Jennifer Chayes, Laszlo Lovasz
For a symmetric bounded measurable function W on [0,1]^2, "moments" of W can be defined as values t(F,W) indexed by simple graphs. We prove that every such function is determined b…