Colección SciELO Chile

Departamento Gestión de Conocimiento, Monitoreo y Prospección
Consultas o comentarios: productividad@anid.cl
Búsqueda Publicación
Búsqueda por Tema Título, Abstract y Keywords



Mixed-integer programming approaches for the tree <i>t</i>*-spanner problem
Indexado
WoS WOS:000485312100016
Scopus SCOPUS_ID:85055714578
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


Abstract



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.

Revista



Revista ISSN
Optimization Letters 1862-4472

Métricas Externas



PlumX Altmetric Dimensions

Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:

Disciplinas de Investigación



WOS
Mathematics, Applied
Operations Research & Management Science
Scopus
Sin Disciplinas
SciELO
Sin Disciplinas

Muestra la distribución de disciplinas para esta publicación.

Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.

Colaboración Institucional



Muestra la distribución de colaboración, tanto nacional como extranjera, generada en esta publicación.


Autores - Afiliación



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

Muestra la afiliación y género (detectado) para los co-autores de la publicación.

Financiamiento



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

Muestra la fuente de financiamiento declarada en la publicación.

Agradecimientos



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).

Muestra la fuente de financiamiento declarada en la publicación.