Statistical mechanics of steiner trees.
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 us to analyze the statistical mechanics properties of MST on random graphs of various types.
Bayati
M
M
Microsoft Research, One Microsoft Way, 98052 Redmond, Washington, USA.
Borgs
C
C
Braunstein
A
A
Chayes
J
J
Ramezanpour
A
A
Zecchina
R
R