M. Bayati, C. Borgs, A. Braunstein, J. Chayes, A. Ramezanpour, R. Zecchina
Published 2008-07-21Version 1
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 technique to translate the imposed global connectivity constrain into many local ones that can be analyzed with cavity equation techniques. This approach leads to a new optimization algorithm for MST and allows to analyze the statistical mechanics properties of MST on random graphs of various types.
Journal: Phys. Rev. Lett. 101, 037208 (2008)
Statistical Mechanics of systems with long range interactions
Application of Edwards' statistical mechanics to high dimensional jammed sphere packings
Statistical Mechanics of the Hyper Vertex Cover Problem
![QR code for arXiv:0807.3373 [cond-mat.stat-mech]](http://oss.arxitics.com/images/favicon.svg)