Título original | Arbres minimals i arbres de Steiner en la mètrica rectilínea. |
---|---|
Título inglés | Shortest trees and Steiner trees with rectilinear distances. |
Título español | Arboles mínimos y árboles de Steiner en la métrica rectilínea. |
Autor/es | Basart, Josep M. ; Huguet, Llorenç |
Organización | Dep. Informàt. Fac. Cienc. Univ. Autòn. Barcelona, Bellaterra (Barcelona), España |
Revista | 0210-8054 |
Publicación | 1988, 12 (2): 159-174, 16 Ref. |
Tipo de documento | articulo |
Idioma | Catalán |
Resumen español | Usando la métrica rectilínea (oL1) se tratan algunos aspectos del problema clásico de hallar el árbol de coste mínimo que enlaza un conjunto dado de P puntos en el plano. En primer lugar se recuerdan las propiedades fundamentales de los árboles de Steiner dado que éstos son la solución general al problema enunciado. A partir de unas observaciones sobre la acotación de su longitud máxima cuando P se halla en el interior de un cuadrado Q de lado unidad, se obtiene -para el mismo caso- una cota superior para la longitud del árbol mínimo dado por el algoritmo de Prim o el de Kruskal. Finalmente, se proporciona un método para construir -cuando existan- árboles de rectángulos de distancia mínima. Estos árboles hacen que el problema inicial sea resoluble mediante métodos polinómicos, quebrando así la característica de NP-completitud que presenta en el caso general la búsqueda de los árboles de Steiner. |
Clasificación UNESCO | 120704 |
Palabras clave español | Arbol minimal ; Problema general de rutas ; Algoritmos ; Distancia mínima ; Grafos ; Interconexión |
Código MathReviews | MR1034893 |
![]() |