Presentación | Participantes | Bibliografía (DML-E) | Bibliografía adicional | Enlaces de interés | Otros proyectos DML | Ayuda  
INICIO | 09 de junio de 2023
  

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
Icono pdf Acceso al artículo completo
Equipo DML-E
Instituto de Ciencias Matemáticas (ICMAT - CSIC)
rmm()icmat.es