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

DOI10.1063/1.2982805zbMath1159.81303arXiv0901.1684OpenAlexW1498489820WikidataQ61444428 ScholiaQ61444428MaRDI QIDQ3624666

Alfredo Braunstein, Mohsen Bayati, Riccardo Zecchina

Publication date: 30 April 2009

Published in: Journal of Mathematical Physics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0901.1684

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Stochastic methods applied to problems in equilibrium statistical mechanics (82B31)

Related Items (4)

Belief propagation for the maximum-weight independent set and minimum spanning tree problems ⋮ The patient-zero problem with noisy observations ⋮ The cavity approach for Steiner trees packing problems ⋮ Convergence and correctness of belief propagation for the Chinese postman problem

Uses Software

• apcluster
• APCluster

Cites Work

• Clustering by Passing Messages Between Data Points
• Correctness of Belief Propagation in Gaussian Graphical Models of Arbitrary Topology
• On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs
• Survey propagation: An algorithm for satisfiability
• Gibbs states and the set of solutions of random constraint satisfaction problems

This page was built for publication: A rigorous analysis of the cavity equations for the minimum spanning tree