A rigorous analysis of the cavity equations for the minimum spanning tree

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We analyze a new general representation for the Minimum Weight Steiner Tree (MST) problem which translates the topological connectivity constraint into a set of local conditions which can be analyzed by the so called cavity equations techniques. For the limit case of the Spanning tree we prove that the fixed point of the algorithm arising from the cavity equations leads to the global optimum.
5 pages, 1 figure

Keywords

Statistical Mechanics, Disordered Systems and Neural Networks, Data Structures and Algorithms

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/215688

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0901.1684
 http://arxiv.org/abs/0901.1684
 J. Math. Phys. 49, 125206 (2008)
 doi:10.1063/1.2982805

Collections

arXiv