Observatorio de I+D+i UPM

Memorias de investigación
Artículos en revistas:
Approximations on Minimum Weight Triangulations and Minimum Weight Pseudo-Triangulations Using Ant Colony Optimization Metaheuristic
Año:2012
Áreas de investigación
  • Algoritmos,
  • Geometría discreta y algorítmica
Datos
Descripción
Globally optimal triangulations and pseudo-triangulations are difficult to be found by deterministic methods as, for most type of criteria, no polynomial algorithm is known. In this work, we consider the Minimum Weight Triangulation (MWT) and Minimum Weight Pseudo-Triangulation (MWPT) problems of a given set of n points in the plane. This paper shows how the Ant Colony Optimization (ACO) metaheuristic can be used to find high quality triangulations and pseudotriangulations of minimum weight. For the experimental study presented here we have created a set of instances for MWT and MWPT problems since no reference to benchmarks for these problems were found in the literature. Through the experimental evaluation, we assess the applicability of the ACO metaheuristic for MWT and MWPT problems
Internacional
Si
JCR del ISI
Si
Título de la revista
Fundamenta Informaticae
ISSN
0169-2968
Factor de impacto JCR
Información de impacto
Volumen
119
DOI
dx.doi.org/10.3233/FI-2012-725
Número de revista
1
Desde la página
1
Hasta la página
27
Mes
SIN MES
Ranking
Esta actividad pertenece a memorias de investigación
Participantes
  • Autor: Gregorio Hernandez Peñalver (UPM)
  • Autor: María Gisela Dorzán (Universidad Nacional de San Luis, Argentina)
  • Autor: Edilma Olinda Gagliardi (Universidad Nacional de San Luis, Argentina)
  • Autor: Mario Guillermo Leguizamón (Universidad Nacional de San Luis, Argentina)
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Departamento: Matemática Aplicada (Facultad de Informática)
S2i 2022 Observatorio de investigación @ UPM con la colaboración del Consejo Social UPM
Cofinanciación del MINECO en el marco del Programa INNCIDE 2011 (OTR-2011-0236)
Cofinanciación del MINECO en el marco del Programa INNPACTO (IPT-020000-2010-22)