| Statistical mechanics of steiner trees. | |
| | |
MedLine Citation:
|
PMID: 18764290 Owner: NLM Status: MEDLINE |
Abstract/OtherAbstract:
|
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:
|
M Bayati; C Borgs; A Braunstein; J Chayes; A Ramezanpour; R Zecchina |
Publication Detail:
|
Type: Journal Article Date: 2008-07-18 |
Journal Detail:
|
Title: Physical review letters Volume: 101 ISSN: 0031-9007 ISO Abbreviation: Phys. Rev. Lett. Publication Date: 2008 Jul |
Date Detail:
|
Created Date: 2008-09-03 Completed Date: 2008-09-16 Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 0401141 Medline TA: Phys Rev Lett Country: United States |
Other Details:
|
Languages: eng Pagination: 037208 Citation Subset: IM |
Affiliation:
|
Microsoft Research, One Microsoft Way, 98052 Redmond, Washington, USA. |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
Algorithms* Models, Statistical* Population Dynamics |
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Scattering theory of gilbert damping.
Next Document: Spin-orbit coupling and ion displacements in multiferroic TbMnO3.