Statistical Mechanics of Steiner Trees

TitleStatistical Mechanics of Steiner Trees
Publication TypeJournal Article
Year of Publication2008
AuthorsBayati M, Borgs C, Braunstein A, Chayes J, Ramezanpour A, Zecchina R
JournalPhysical Review Letters

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 to analyze the statistical mechanics properties of MST on random graphs of various types.

prl-steiner.pdf210.2 KB