Statistical Mechanics of Steiner Trees

M. Bayati, C. Borgs, A. Braunstein, J. Chayes, A. Ramezanpour, and R. Zecchina
Phys. Rev. Lett. 101, 037208 – Published 18 July 2008

Abstract

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.

  • Figure
  • Figure
  • Figure
  • Received 5 May 2008

DOI:https://doi.org/10.1103/PhysRevLett.101.037208

©2008 American Physical Society

Authors & Affiliations

M. Bayati1, C. Borgs1, A. Braunstein2, J. Chayes1, A. Ramezanpour3, and R. Zecchina2

  • 1Microsoft Research, One Microsoft Way, 98052 Redmond, Washington, USA
  • 2Politecnico di Torino, Corso Duca degli Abruzzi 24, 10129 Torino, Italy
  • 3ICTP, Strada Costiera 11, I-34100 Trieste, Italy

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 101, Iss. 3 — 18 July 2008

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review Letters

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×