Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:
| Indexado |
|
||||
| DOI | 10.1007/S11590-018-1340-0 | ||||
| Año | 2019 | ||||
| Tipo | artículo de investigación |
Citas Totales
Autores Afiliación Chile
Instituciones Chile
% Participación
Internacional
Autores
Afiliación Extranjera
Instituciones
Extranjeras
The tree-spanner problem is an NP-hard problem, which is concerned with finding a spanning tree in a given undirected weighted graph, such that for each pair of nodes the ratio of the shortest distance in the spanning tree and the shortest distance in the given graph is bounded by t. The goal is to find a spanning tree, which gives the minimal t. This problem is associated with many network design applications, but in particular, in the context of architecture of distributed systems. We introduce mixed-integer programming formulations for the tree -spanner problem, and present a branch-and-cut solution approach based on these formulations. The branch-and-cut is enhanced with an initialization procedure and a primal heuristic. A computational study is done to assess the effectiveness of our proposed algorithmic strategies. To the best of our knowledge, this is the first time that an exact approach is proposed for this problem.
| Ord. | Autor | Género | Institución - País |
|---|---|---|---|
| 1 | ALVAREZ-MIRANDA, EDUARDO ANDRE | Hombre |
Universidad de Talca - Chile
|
| 2 | Sinnl, Markus | Hombre |
INRIA Lille Nord Europe - Francia
INRIA Institut National de Recherche en Informatique et en Automatique - Francia |
| Fuente |
|---|
| Fondo Nacional de Desarrollo Científico y Tecnológico |
| Comisión Nacional de Investigación Científica y Tecnológica |
| Comisión Nacional de Investigación CientÃfica y Tecnológica |
| Fondo Nacional de Desarrollo CientÃfico y Tecnológico |
| Instituto de Sistemas Complejos de Ingeniería |
| Chilean Council of Scientific and Technological Research, CONICYT, through the grant FONDECYT |
| Chilean Council of Scientific and Technological Research, CONICYT through the Complex Engineering Systems Institute |
| Chilean Council of Scientific and Technological Research |
| Instituto de Sistemas Complejos de IngenierÃa |
| Consejo Nacional para Investigaciones CientÃficas y Tecnológicas |
| Agradecimiento |
|---|
| E.A.-M. acknowledges the support of the Chilean Council of Scientific and Technological Research, CONICYT, through the grant FONDECYT N. 1180670 and through the Complex Engineering Systems Institute (ICM-FIC: P-05-004-F, CONICYT: FB0816). |
| E.A.-M. acknowledges the support of the Chilean Council of Scientific and Technological Research, CONICYT, through the grant FONDECYT N. 1180670 and through the Complex Engineering Systems Institute (ICM-FIC:P-05-004-F, CONICYT:FB0816). |