Título: Modelling the diameter-constrained  minimum spanning tree 
problem over a layered graph

Palestrante: Luidi Simonetti (UFRJ)

Resumo

Given a undirected graph G = (V, E)  with node set V and edge set E as
well as  a cost  ce associated with  each edge  e of E,  the diameter-
constrained  minimum spanning  tree problem  (DMST) seek  minimum cost
spanning  trees with  a limit  D imposed  upon the  length  (number of
edges) of any path in  the tree. The diameter restriction guarantees a
specified  level  of  service  with  respect  to  certain  performance
measures; for example, it guarantees a prescribed level of reliability
to potential link or node failures.  The problem is easy to solve when
D = 2 or 3 and is NP-Hard when D >= 4.

We  propose a modelling  approach for  the DMST  that views  the whole
problem as defined in an  appropriate layered directed graph. In fact,
this is equivalent to a  transformation to a suitable directed Steiner
tree  problem   over  that  layered   graph.  Extensive  computational
experiments show that almost all  instances from the literature can be
solved without  branching.  The overall  approach is shown to  be very
efficient. Instances with  up to 80 nodes can  be solved in reasonable
times, a significant increase with respect to previous methods.