MÉTODOS COMPUTACIONALES ORIENTADOS A LA OBTENCIÓN DEL ÁRBOL EMST: UN APORTE AL PROBLEMA DE STEINER

Pablo López, Carlos Yañez Duràn, Luzmila Pro Concepción, Jaime Alcalde

Resumen


Un Árbol Recubridor Euclídeo Mínimo (EMST: Euclidean Minimum Spanning Tree) es un árbol o subgrafo sin ciclos, que permite interconectar todos los vértices y minimizar la longitud total de las aristas de un grafo determinado. No obstante esta minimización, a través de la adición de nuevos vértices al conjunto original se logra efectuar una minimización más óptima. Estos árboles se denominan Árboles de Steiner y tienen grandes aplicaciones, particularmente en el diseño de redes de transportes y de comunicaciones. Resultados esperados: Obtención del Árbol EMST.

Palabras clave


Árbol EMST, Árbol de Steiner, Algoritmo Genético.

Texto completo:

PDF

Enlaces refback

  • No hay ningún enlace refback.




Copyright (c) 2014 Pablo López, Carlos Yañez Duràn, Luzmila Pro Concepción, Jaime Alcalde

Licencia de Creative Commons
Este obra está bajo una licencia de Creative Commons Reconocimiento-NoComercial-CompartirIgual 4.0 Internacional.

 

 



Facultad de Ingeniería de Sistemas e Informática, Universidad Nacional Mayor de San Marcos, Lima, Perú Teléfono: (511) 619 7000 (anexo 3604) Correo electrónico: investigacion@sistemas.edu.pe.