2008/07/18 by M. Bayati, Mohsen Bayati, C. Borgs +9 · 4 citations
Computer Science · Physics and Astronomy · #Advanced Graph Theory Research #Complex Network Analysis Techniques #Complexity and Algorithms in Graphs #cond-mat.dis-nn #cond-mat.stat-mech
paper · pdf · doi:10.1103/physrevlett.101.037208
published as Phys. Rev. Lett. 101, 037208 (2008)
openalex publication_date 2008/07/18 · arxiv created 2008/07/21 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.