Statistical mechanics of Steiner trees

被引：34

作者：

Bayati, M. ^{[1
]}

Borgs, C. ^{[1
]}

Braunstein, A. ^{[2
]}

Chayes, J. ^{[1
]}

Ramezanpour, A. ^{[3
]}

Zecchina, R. ^{[2
]}

机构：

[1] Microsoft Res, Redmond, WA 98052 USA

[2] Politecn Torino, I-10129 Turin, Italy

[3] ICTP, I-34100 Trieste, Italy

来源：

PHYSICAL REVIEW LETTERS | 2008年 / 101卷 / 03期

关键词：

D O I：

10.1103/PhysRevLett.101.037208

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

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.

引用

页数：4

共 18 条

[1]

ADDARIOBERRY L, 2006, P 4 C MATH COMP SCI

[2] The ζ(2) limit in the random assignment problem [J].