Speaker
Prof.
Riccardo Zecchina
(Politecnico di Torino)
Description
Given an undirected graph with positive weights on the
edges, the Minimum Weight Steiner Tree (MST) problem
consists in finding a connected subgraph of minimum weight
that contains a selected set of ``terminal'' vertices. Such
construction may require the inclusion of some non-terminal
nodes which are called Steiner nodes. Clearly, an optimal
sub-graph must be a tree. Solving MST is a key component of
many optimization problems involving real networks. 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 MSTs on random graphs of various types.
This approach leads to a new optimization algorithm for MST and allows to analyze the statistical mechanics properties of MSTs on random graphs of various types.
