Observatorio de I+D+i UPM

Memorias de investigación
Artículos en revistas:
Network design through forests with degree- and role- constrained minimum spanning trees
Año:2017
Áreas de investigación
  • Inteligencia artificial
Datos
Descripción
Dendritic spines establish most excitatory synapses in the brain and are Finding the degree-constrained minimum spanning tree (DCMST) of a graph is a widely studied NP-hard problem. One of its most important applications is network design. Here we deal with a new variant of the DCMST problem, which consists of finding not only the degree- but also the role-constrained minimum spanning tree (DRCMST), i.e., we add constraints to restrict the role of the nodes in the tree to root, intermediate or leaf node. Furthermore, we do not limit the number of root nodes to one, thereby, generally, building a forest of DRCMSTs. The modeling of network design problems can benefit from the possibility of generating more than one tree and determining the role of the nodes in the network. We propose a novel permutation-based representation to encode these forests. In this new representation, one permutation simultaneously encodes all the trees to be built. We simulate a wide variety of DRCMST problem instances which we optimize using different evolutionary computation algorithms encoding individuals of the population using the proposed representation. To illustrate the applicability of our approach, we formulate the trans-European transport network as a DRCMST problem. In this network design, we simultaneously optimize nine transport corridors and show that it is straightforward using the proposed representation to add constraints depending on the specific characteristics of the network.
Internacional
Si
JCR del ISI
Si
Título de la revista
Journal of Heuristics
ISSN
1381-1231
Factor de impacto JCR
1,344
Información de impacto
Datos JCR del año 2015
Volumen
23
DOI
Número de revista
1
Desde la página
31
Hasta la página
51
Mes
SIN MES
Ranking
Ranking: 36/105 (Quartile 2). Category: Computer science, theory & methods
Esta actividad pertenece a memorias de investigación
Participantes
  • Autor: Laura Anton Sanchez (UPM)
  • Autor: Maria Concepcion Bielza Lozoya (UPM)
  • Autor: Pedro Maria Larrañaga Mugica (UPM)
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Departamento: Inteligencia Artificial
S2i 2021 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)