Arbres minimals i arbres de Steiner en la mètrica rectilínea.

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
Acceso al artículo completo