Statistical mechanics of Steiner trees
Statistical mechanics of Steiner trees
复制标题
DOI：
10.1103/physrevlett.101.037208
复制
发表时间：
2008-07-18
影响因子：
8.6
通讯作者：
Zecchina, R.
中科院分区：
文献类型：
--
作者：
Bayati, M.;Borgs, C.;Zecchina, R.
最小权Steiner树（MST）是一个重要的网络组合优化问题，在许多领域有着广泛的应用。在这里，我们讨论了一种通用的技术，将强加的全球连接约束转化为许多本地的，可以与腔方程技术进行分析。这种方法导致一个新的优化算法MST，并允许我们分析的统计力学性质的MST的随机图的各种类型。
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.