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.
@article{urn:eudml:doc:40143,
title = {Arbres minimals i arbres de Steiner en la m\`etrica rectil\'\i nea.},
journal = {Q\"uestii\'o},
volume = {12},
year = {1988},
pages = {159-174},
mrnumber = {MR1034893},
zbl = {1167.05306},
language = {ca},
url = {http://dml.mathdoc.fr/item/urn:eudml:doc:40143}
}
Basart, Josep M.; Huguet, Llorenç. Arbres minimals i arbres de Steiner en la mètrica rectilínea.. Qüestiió, Tome 12 (1988) pp. 159-174. http://gdmltest.u-ga.fr/item/urn:eudml:doc:40143/