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

Simple item page
dc.creatorBayati, M.
dc.creatorBraunstein, A.
dc.creatorZecchina, R.
dc.date2009-01-12
dc.date.accessioned2026-07-07T12:28:52Z
dc.date.available2026-07-07T12:28:52Z
dc.descriptionWe 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.
dc.description5 pages, 1 figure
dc.identifierhttps://arxiv.org/abs/0901.1684
dc.identifierhttp://arxiv.org/abs/0901.1684
dc.identifierJ. Math. Phys. 49, 125206 (2008)
dc.identifierdoi:10.1063/1.2982805
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/215688
dc.subjectStatistical Mechanics
dc.subjectDisordered Systems and Neural Networks
dc.subjectData Structures and Algorithms
dc.titleA rigorous analysis of the cavity equations for the minimum spanning tree
dc.typetext

Files

Collections

arXiv