Statistical Mechanics of Steiner trees

Abstract

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.

References in corpus (5)

• The Bethe lattice spin glass revisited
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Learning by message-passing in networks of discrete synapses
• Polynomial iterative algorithms for coloring and analyzing random graphs
• Structure of Optimal Transport Networks Subject to a Global Constraint

Cited by in corpus (28)

• Spatial Networks
• Vital nodes identification in complex networks
• Containing epidemic outbreaks by message-passing techniques
• Finding undetected protein associations in cell signaling by belief propagation
• Spin glass approach to the feedback vertex set problem
• Optimizing spread dynamics on graphs by message passing
• Networking - A Statistical Physics Perspective
• The Cavity Approach to Parallel Dynamics of Ising Spins on a Graph
• Comprehensive routing strategy on multilayer networks
• Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives
• The Competition for Shortest Paths on Sparse Graphs
• Aligning graphs and finding substructures by a cavity approach
• A rigorous analysis of the cavity equations for the minimum spanning tree
• Solving the undirected feedback vertex set problem by local search
• On the performance of a cavity method based algorithm for the Prize-Collecting Steiner Tree Problem on graphs
• Network extraction by routing optimization
• Stochastic optimization by message passing
• A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks
• The edge-disjoint path problem on random graphs by message-passing
• Clustering with shallow trees
• Sign problem in the Bethe approximation
• The Futility of Being Selfish -- The Impact of Selfish Routing on Uncoordinated and Optimized Transportation Networks
• Feedback arcs and node hierarchy in directed networks
• Optimal transport with constraints: from mirror descent to classical mechanics
• The cavity approach for Steiner trees packing problems
• Practical optimization of Steiner Trees via the cavity method
• A Message Passing Algorithm for the Problem of Path Packing in Graphs
• A cavity approach to optimization and inverse dynamical problems