title: Statistical mechanics of steiner trees.
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.
authors.affiliation: Microsoft Research, One Microsoft Way, 98052 Redmond, Washington, USA.
authors.forename: M
authors.initials: M
authors.lastname: Bayati
authors.forename: C
authors.initials: C
authors.lastname: Borgs
authors.forename: A
authors.initials: A
authors.lastname: Braunstein
authors.forename: J
authors.initials: J
authors.lastname: Chayes
authors.forename: A
authors.initials: A
authors.lastname: Ramezanpour
authors.forename: R
authors.initials: R
authors.lastname: Zecchina