Problema del árbol de Steiner

En redes de conexión cortas con vértices agregados

Árbol de Steiner para tres puntos A , B y C (tenga en cuenta que no hay conexiones directas entre A , B , C ). El punto Steiner S está situado en el punto Fermat del triángulo ABC .

Solución para cuatro puntos: hay dos puntos Steiner, S ₁ y S ₂

En matemáticas combinatorias , el problema del árbol de Steiner , o problema del árbol de Steiner mínimo , llamado así en honor a Jakob Steiner , es un término general para una clase de problemas en optimización combinatoria . Si bien los problemas del árbol de Steiner pueden formularse en varios entornos, todos requieren una interconexión óptima para un conjunto determinado de objetos y una función objetivo predefinida . Una variante muy conocida, que a menudo se utiliza como sinónimo del término problema del árbol de Steiner, es el problema del árbol de Steiner en gráficos . Dado un gráfico no dirigido con pesos de aristas no negativos y un subconjunto de vértices, generalmente denominados terminales, el problema del árbol de Steiner en gráficos requiere un árbol de peso mínimo que contenga todos los terminales (pero puede incluir vértices adicionales) y minimice el peso total. de sus bordes. Otras variantes conocidas son el problema del árbol euclidiano de Steiner y el problema del árbol de Steiner mínimo rectilíneo .

El problema del árbol de Steiner en gráficos puede verse como una generalización de otros dos famosos problemas de optimización combinatoria: el problema del camino más corto (no negativo) y el problema del árbol de expansión mínima . Si un problema de árbol de Steiner en gráficos contiene exactamente dos terminales, se reduce a encontrar el camino más corto. Si, por el contrario, todos los vértices son terminales, el problema del árbol de Steiner en gráficos equivale al árbol de expansión mínima. Sin embargo, si bien tanto el camino más corto no negativo como el problema del árbol de expansión mínima se pueden resolver en tiempo polinomial , no se conoce tal solución para el problema del árbol de Steiner. Su variante de decisión , que pregunta si una entrada determinada tiene un árbol con un peso inferior a un umbral determinado, es NP-completa , lo que implica que la variante de optimización, que pregunta por el árbol de peso mínimo en un gráfico determinado, es NP-dura . De hecho, la variante de decisión estaba entre los 21 problemas NP completos originales de Karp . El problema del árbol de Steiner en gráficos tiene aplicaciones en el trazado de circuitos o en el diseño de redes . Sin embargo, las aplicaciones prácticas suelen requerir variaciones, dando lugar a multitud de variantes del problema del árbol de Steiner.

La mayoría de las versiones del problema del árbol de Steiner son NP-difíciles, pero algunos casos restringidos se pueden resolver en tiempo polinomial. A pesar de la complejidad pesimista del peor de los casos , varias variantes del problema del árbol de Steiner, incluido el problema del árbol de Steiner en gráficos y el problema del árbol de Steiner rectilíneo, se pueden resolver de manera eficiente en la práctica, incluso para problemas del mundo real a gran escala. ^{[1] [2]}

Árbol euclidiano de Steiner

Árboles Steiner mínimos de vértices de polígonos regulares con N = 3 a 8 lados. La longitud de red más baja L para N > 5 es la circunferencia menos un lado. Los cuadrados representan puntos Steiner.

El problema original se planteó en la forma que se conoce como problema del árbol euclidiano de Steiner o problema geométrico del árbol de Steiner : dados N puntos en el plano , el objetivo es conectarlos mediante líneas de longitud total mínima de tal manera que dos Los puntos pueden estar interconectados por segmentos de línea, ya sea directamente o mediante otros puntos y segmentos de línea.

Si bien el problema lleva el nombre de Steiner, fue planteado por primera vez en 1811 por Joseph Diez Gergonne de la siguiente forma: "Varias ciudades están ubicadas en lugares conocidos en un plano; el problema es unirlas entre sí mediante un sistema de canales". cuya longitud total sea lo más pequeña posible". ^[3]

Se puede demostrar que los segmentos de línea que los conectan no se cruzan entre sí excepto en los puntos finales y forman un árbol, de ahí el nombre del problema.

El problema de N  = 3 se ha considerado durante mucho tiempo y rápidamente se amplió al problema de encontrar una red en estrella con un único centro que conecte a todos los N puntos dados, de longitud total mínima. Sin embargo, aunque el problema completo del árbol de Steiner fue formulado en una carta de Gauss , su primer tratamiento serio fue en un artículo de 1934 escrito en checo por Vojtěch Jarník y Miloš Kössler  [cs] . Este artículo fue pasado por alto durante mucho tiempo, pero ya contiene "prácticamente todas las propiedades generales de los árboles de Steiner" atribuidas más tarde a otros investigadores, incluida la generalización del problema desde el plano a dimensiones superiores. ^[4]

Para el problema euclidiano de Steiner, los puntos agregados al gráfico ( puntos de Steiner ) deben tener un grado de tres, y las tres aristas incidentes en dicho punto deben formar tres ángulos de 120 grados (ver punto de Fermat ). De ello se deduce que el número máximo de puntos Steiner que puede tener un árbol Steiner es N  − 2, donde N es el número inicial de puntos dados. (Todas estas propiedades ya fueron establecidas por Gergonne.)

Para N = 3 hay dos casos posibles: si el triángulo formado por los puntos dados tiene todos los ángulos menores de 120 grados, la solución viene dada por un punto de Steiner ubicado en el punto de Fermat ; de lo contrario, la solución viene dada por los dos lados del triángulo que se encuentran en un ángulo de 120 grados o más.

Para N general , el problema del árbol euclidiano de Steiner es NP-difícil y, por lo tanto, no se sabe si se puede encontrar una solución óptima utilizando un algoritmo de tiempo polinomial . Sin embargo, existe un esquema de aproximación en tiempo polinomial (PTAS) para árboles euclidianos de Steiner, es decir, se puede encontrar una solución casi óptima en tiempo polinomial. ^[5] No se sabe si el problema del árbol euclidiano de Steiner es NP-completo, ya que se desconoce la pertenencia a la clase de complejidad NP.

Árbol Steiner rectilíneo

El problema del árbol de Steiner rectilíneo es una variante del problema del árbol de Steiner geométrico en el plano, en el que la distancia euclidiana se reemplaza por la distancia rectilínea . El problema surge en el diseño físico de la automatización del diseño electrónico . En los circuitos VLSI , el enrutamiento de cables se realiza mediante cables que a menudo están restringidos por reglas de diseño a correr solo en direcciones verticales y horizontales, por lo que el problema del árbol rectilíneo de Steiner se puede utilizar para modelar el enrutamiento de redes con más de dos terminales. ^[6]

Árbol de Steiner en gráficos y variantes.

Los árboles de Steiner se han estudiado ampliamente en el contexto de gráficos ponderados . Podría decirse que el prototipo es el problema del árbol de Steiner en gráficos . Sea G  = ( V ,  E ) un gráfico no dirigido con pesos de aristas no negativos c y sea S  ⊆  V un subconjunto de vértices, llamados terminales . Un árbol de Steiner es un árbol en G que se extiende por S. Hay dos versiones del problema: en el problema de optimización asociado con los árboles Steiner, la tarea es encontrar un árbol Steiner de peso mínimo; en el problema de decisión los pesos de las aristas son números enteros y la tarea es determinar si existe un árbol de Steiner cuyo peso total no exceda un número natural predefinido k . El problema de decisión es uno de los 21 problemas NP-completos de Karp ; por tanto, el problema de optimización es NP-difícil . Los problemas del árbol de Steiner en gráficos se aplican a diversos problemas en la investigación y la industria, ^[7] incluido el enrutamiento de multidifusión ^[8] y la bioinformática. ^[9]

Un caso especial de este problema es cuando G es un gráfico completo , cada vértice v  ∈  V corresponde a un punto en un espacio métrico , y los pesos de las aristas w ( e ) para cada e  ∈  E corresponden a distancias en el espacio. Dicho de otra manera, los pesos de las aristas satisfacen la desigualdad del triángulo . Esta variante se conoce como problema del árbol métrico de Steiner . Dada una instancia del problema del árbol de Steiner (no métrico), podemos transformarla en tiempo polinomial en una instancia equivalente del problema del árbol de Steiner métrico; la transformación conserva el factor de aproximación. ^[10]

Si bien la versión euclidiana admite un PTAS, se sabe que el problema métrico del árbol de Steiner es APX-completo , es decir, a menos que P = NP , es imposible lograr relaciones de aproximación que sean arbitrariamente cercanas a 1 en tiempo polinomial. Existe un algoritmo de tiempo polinomial que aproxima el árbol de Steiner mínimo dentro de un factor de ; ^[11] sin embargo, aproximarse dentro de un factor es NP-difícil. ^[12] Para el caso restringido del problema del árbol de Steiner con distancias 1 y 2, se conoce un algoritmo de aproximación de 1,25. ^[13] Karpinski y Alexander Zelikovsky construyeron PTAS para los casos densos de problemas del árbol de Steiner. ^[14] ${\displaystyle \ln(4)+\varepsilon \approx 1.386}$ ${\displaystyle 96/95\approx 1.0105}$

En un caso especial del problema de gráficos, el problema del árbol de Steiner para gráficos cuasi-bipartitos , se requiere que S incluya al menos un punto final de cada arista en G.

El problema del árbol de Steiner también se ha investigado en dimensiones superiores y en diversas superficies. Se han encontrado algoritmos para encontrar el árbol mínimo de Steiner en la esfera, el toro, el plano proyectivo , los conos anchos y estrechos, y otros. ^[15]

Otras generalizaciones del problema del árbol de Steiner son el problema de la red Steiner con k -borde conectado y el k -problema de la red Steiner conectado con vértice , donde el objetivo es encontrar un gráfico k -conectado con borde o un gráfico k -conectado con vértice en lugar de que cualquier gráfico conectado. Otra generalización bien estudiada ^{[16] es el} problema de diseño de red de supervivencia (SNDP), donde la tarea es conectar cada par de vértices con un número determinado (posiblemente 0) de rutas de borde o de vértice disjuntas.

El problema de Steiner también se ha planteado en el ámbito general de los espacios métricos y posiblemente para una infinidad de puntos. ^[17]

Aproximación al árbol de Steiner

El problema del árbol de Steiner del gráfico general se puede aproximar calculando el árbol de expansión mínimo del subgrafo del cierre métrico del gráfico inducido por los vértices terminales, publicado por primera vez en 1981 por Kou et al. ^[18] El cierre métrico de un gráfico G es el gráfico completo en el que cada borde está ponderado por la distancia del camino más corto entre los nodos en G. Este algoritmo produce un árbol cuyo peso está dentro de un factor 2 − 2/ t del peso del árbol Steiner óptimo donde t es el número de hojas en el árbol Steiner óptimo; Esto puede comprobarse considerando un recorrido de un vendedor ambulante por el árbol de Steiner óptimo. Esta solución aproximada es computable en tiempo polinómico O(|S| |V|²) resolviendo primero el problema de caminos más cortos de todos los pares para calcular el cierre métrico y luego resolviendo el problema del árbol de expansión mínimo .

Takahashi y Matsuyama publicaron otro algoritmo popular para aproximar el árbol de Steiner en gráficos en 1980. ^[19] Su solución construye incrementalmente el árbol de Steiner comenzando desde un vértice arbitrario y agregando repetidamente el camino más corto desde el árbol hasta el vértice más cercano. en S que aún no se ha agregado. Este algoritmo también tiene un tiempo de ejecución O(| S | | V |²) y produce un árbol cuyo peso está dentro de 2 − 2/| S | de óptimo.

En 1986, Wu et al. ^[20] mejoraron drásticamente el tiempo de ejecución al evitar el cálculo previo de los caminos más cortos de todos los pares. En cambio, adoptan un enfoque similar al algoritmo de Kruskal para calcular un árbol de expansión mínimo, partiendo de un bosque de | S | árboles disjuntos y "hacerlos crecer" simultáneamente utilizando una búsqueda en amplitud similar al algoritmo de Dijkstra pero comenzando desde múltiples vértices iniciales. Cuando la búsqueda encuentra un vértice que no pertenece al árbol actual, los dos árboles se fusionan en uno. Este proceso se repite hasta que solo quede un árbol. Al utilizar un montón (estructura de datos) para implementar la cola de prioridad y una estructura de datos de conjunto disjunto para rastrear a qué árbol pertenece cada vértice visitado, este algoritmo logra un tiempo de ejecución O(| E | log | V |), aunque no mejorar la relación de costos 2 − 2/ t de Kou et al.

Una serie de artículos proporcionaron algoritmos de aproximación para el problema del árbol de Steiner mínimo con relaciones de aproximación que mejoraron la relación 2 − 2/ t . Esta secuencia culminó con el algoritmo de Robins y Zelikovsky en 2000, que mejoró la relación a 1,55 mejorando iterativamente el árbol de expansión de terminales de costo mínimo. Sin embargo, más recientemente, Byrka et al. demostró una aproximación utilizando una relajación de programación lineal y una técnica llamada redondeo aleatorio iterativo. ^[11] ${\displaystyle \ln(4)+\varepsilon \leq 1.39}$

Complejidad parametrizada del árbol de Steiner.

Se sabe que el problema del árbol de Steiner del gráfico general es manejable con parámetros fijos , con el número de terminales como parámetro, mediante el algoritmo de Dreyfus-Wagner. ^{[21] [22]} El tiempo de ejecución del algoritmo de Dreyfus-Wagner es , donde es el número de vértices del gráfico y es el conjunto de terminales. Existen algoritmos más rápidos, que se ejecutan en el tiempo para cualquier o, en el caso de pesos pequeños, en el tiempo, donde es el peso máximo de cualquier borde. ^{[23] [24]} Una desventaja de los algoritmos antes mencionados es que utilizan espacio exponencial ; Existen algoritmos de espacio polinómico que se ejecutan en el tiempo y en el tiempo. ^{[25] [26]} ${\displaystyle 3^{|S|}{\text{poly}}(n)}$ ${\displaystyle n}$ ${\displaystyle S}$ ${\displaystyle c^{|S|}{\text{poly}}(n)}$ ${\displaystyle c>2}$ ${\displaystyle 2^{|S|}{\text{poly}}(n)W}$ ${\displaystyle W}$ ${\displaystyle 2^{|S|}{\text{poly}}(n)W}$ ${\displaystyle (7.97)^{|S|}{\text{poly}}(n)\log W}$

Se sabe que el problema del árbol de Steiner del grafo general no tiene un algoritmo parametrizado que se ejecuta en el tiempo para any , donde es el número de aristas del árbol de Steiner óptimo, a menos que el problema de cobertura del conjunto tenga un algoritmo que se ejecuta en el tiempo para some , donde y son el número de elementos y el número de conjuntos, respectivamente, de la instancia del problema de cobertura de conjuntos. ^[27] Además, se sabe que el problema no admite un núcleo polinómico a menos que esté parametrizado por el número de aristas del árbol Steiner óptimo y si todos los pesos de las aristas son 1. ^[28] ${\displaystyle 2^{\epsilon t}{\text{poly}}(n)}$ ${\displaystyle \epsilon <1}$ ${\displaystyle t}$ ${\displaystyle 2^{\epsilon n}{\text{poly}}(m)}$ ${\displaystyle \epsilon <1}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle {\text{coNP}}\subseteq {\text{NP/poly}}}$

Aproximación parametrizada del árbol de Steiner

Si bien el problema del árbol de Steiner del grafo no admite un núcleo polinómico a menos que esté parametrizado por el número de terminales, sí admite un esquema de kernelización aproximado de tamaño polinómico (PSAKS): para cualquiera es posible calcular un núcleo de tamaño polinómico, que sólo pierde un factor en la calidad de la solución. ^[29] ${\displaystyle {\text{coNP}}\subseteq {\text{NP/poly}}}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle 1+\varepsilon }$

Al parametrizar el problema del árbol de Steiner del gráfico por el número de no terminales (vértices de Steiner) en la solución óptima, el problema es W[1]-difícil (en contraste con la parametrización por el número de terminales, como se mencionó anteriormente). Al mismo tiempo, el problema es APX completo y, por lo tanto, no admite un PTAS , a menos que P = NP . Sin embargo, existe un esquema de aproximación parametrizado que para cualquier calcula una aproximación en el tiempo. ^[30] También existe un PSAKS para esta parametrización. ^[30] ${\displaystyle p}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle (1+\varepsilon )}$ ${\displaystyle 2^{O(p^{2}/\varepsilon ^{4})}n^{O(1)}}$

proporción de Steiner

La relación de Steiner es el supremo de la relación entre la longitud total del árbol de expansión mínimo y el árbol de Steiner mínimo para un conjunto de puntos en el plano euclidiano. ^[31]

En el problema del árbol euclidiano de Steiner, se conjetura que la razón de Steiner es , la razón que se logra mediante tres puntos en un triángulo equilátero con un árbol generador que usa dos lados del triángulo y un árbol de Steiner que conecta los puntos a través del centroide de el triangulo. A pesar de las afirmaciones anteriores de una prueba, ^[32] la conjetura aún está abierta. ^{[33] El} límite superior más ampliamente aceptado para el problema es 1,2134, por Chung y Graham (1985). ${\displaystyle {\tfrac {2}{\sqrt {3}}}\approx 1.1547}$

Para el problema del árbol de Steiner rectilíneo, la relación de Steiner es exactamente , la relación que se logra mediante cuatro puntos en un cuadrado con un árbol de expansión que usa tres lados del cuadrado y un árbol de Steiner que conecta los puntos a través del centro del cuadrado. ^[34] Más precisamente, para la distancia el cuadrado debe estar inclinado con respecto a los ejes de coordenadas, mientras que para la distancia el cuadrado debe estar alineado con el eje. ${\displaystyle {\tfrac {3}{2}}}$ ${\displaystyle L_{1}}$ ${\displaystyle 45^{\circ }}$ ${\displaystyle L_{\infty }}$

Ver también

• Problema del bosque opaco
• Problema del vendedor ambulante

Notas

1. Rehfeldt y Koch (2023).
2. Juhl y col. (2018).
3. Marcus Brazil, Ronald L. Graham, Doreen A. Thomas y Martin Zachariasen, "Sobre la historia del problema del árbol euclidiano Steiner", JSTOR  24569605
4. Korte, Bernhard ; Nešetřil, Jaroslav (2001), "El trabajo de Vojtěch Jarnik en optimización combinatoria", Matemáticas discretas , 235 (1–3): 1–17, doi :10.1016/S0012-365X(00)00256-9, hdl : 10338.dmlcz/ 500662 , señor  1829832.
5. Crescenzi y col. (2000).
6. Sherwani (1993), pág. 228.
7. Ljubić, Ivana (2021). "Resolver árboles de Steiner: avances, desafíos y perspectivas recientes". Redes . 77 (2): 177–204. doi :10.1002/net.22005. ISSN  1097-0037. S2CID  229458488.
8. Novak, romano; Rugelj, Joz̆e; Kandus, Gorazd (1 de octubre de 2001). "Una nota sobre el enrutamiento de multidifusión distribuida en redes punto a punto". Investigación de operaciones y computadoras . 28 (12): 1149-1164. doi :10.1016/S0305-0548(00)00029-0. ISSN  0305-0548.
9. Klimm, Florián; Toledo, Enrique M.; Monfeuga, Tomás; Zhang, colmillo; Deane, Charlotte M.; Reinert, Gesine (2 de noviembre de 2020). "Detección de módulos funcionales mediante la integración de datos de secuenciación de ARN unicelular con redes de interacción proteína-proteína". Genómica BMC . 21 (1): 756. doi : 10.1186/s12864-020-07144-2 . ISSN  1471-2164. PMC 7607865 . PMID  33138772. 
10. Vazirani (2003), págs. 27-28.
11. Byrka y col. (2010).
12. Chlebík y Chlebíková (2008).
13. Berman, Karpinski y Zelikovsky (2009).
14. Karpinski y Zelikovsky (1998).
15. Smith y Winter (1995), pág. 361.
16. Kerivin, Hervé; Mahjoub, A. Ridha (2005). "Diseño de redes de supervivencia: una encuesta". Redes . 46 (1): 1–21. doi :10.1002/net.20072. ISSN  0028-3045. S2CID  8165318.
17. Paolini y Stepanov (2012).
18. Kou, Markowsky y Berman (1981).
19. Takahashi y Matsuyama (1980).
20. Wu, Widmayer y Wong (1986).
21. Dreyfus y Wagner (1971).
22. Levin (1971).
23. Fuchs y col. (2007).
24. Björklund y col. (2007).
25. Lokshtanov y Nederlof (2010).
26. Fomín y col. (2015).
27. Cygan y col. (2016).
28. Dom, Lokshtanov y Saurabh (2014).
29. Lokshtanov, Daniel; Panolan, Fahad; Ramanujan, MS; Saurabh, Saket (19 de junio de 2017). "Kernelización con pérdida". Actas del 49º Simposio anual ACM SIGACT sobre teoría de la informática (PDF) . STOC 2017. Nueva York, NY, EE. UU.: Asociación de Maquinaria de Computación. págs. 224-237. doi :10.1145/3055399.3055456. ISBN 978-1-4503-4528-6. S2CID  14599219.
30. Dvořák, Pavel; Feldmann, Andreas E.; Knop, Dušan; Masařík, Tomáš; Toufar, Tomaš; Veselý, Pavel (1 de enero de 2021). "Esquemas de aproximación parametrizada para árboles Steiner con un pequeño número de vértices Steiner". Revista SIAM de Matemática Discreta . 35 (1): 546–574. arXiv : 1710.00668 . doi :10.1137/18M1209489. ISSN  0895-4801. S2CID  3581913.
31. Ganley (2004).
32. The New York Times , 30 de octubre de 1990, informó que se había encontrado una prueba y que Ronald Graham , que había ofrecido 500 dólares por una prueba, estaba a punto de enviar un cheque a los autores.
33. Ivanov y Tuzhilin (2012).
34. Hwang (1976).

Referencias

• Berman, Piotr; Karpinski, Marek ; Zelikovsky, Alejandro (2009). "Algoritmo de aproximación 1,25 para el problema del árbol de Steiner con distancias 1 y 2". Algoritmos y estructuras de datos: 11.º Simposio internacional, WADS 2009, Banff, Canadá, 21 al 23 de agosto de 2009, Actas . Apuntes de conferencias sobre informática. vol. 5664, págs. 86–97. arXiv : 0810.1851 . doi :10.1007/978-3-642-03367-4_8.
• Berna, Marshall W.; Graham, Ronald L. (1989). "El problema de la red más corta". Científico americano . 260 (1): 84–89. Código Bib : 1989SciAm.260a..84B. doi : 10.1038/scientificamerican0189-84.
• Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko (2007). "Fourier se encuentra con Möbius: convolución de subconjunto rápida". Actas del 39º Simposio ACM sobre Teoría de la Computación . págs. 67–74. arXiv : cs/0611101 . doi :10.1145/1250790.1250801.
• Byrka, J.; Grandoni, F.; Rothvoß, T.; Sanita, L. (2010). "Una aproximación mejorada basada en LP para el árbol de Steiner". Actas del 42º Simposio ACM sobre Teoría de la Computación . págs. 583–592. CiteSeerX  10.1.1.177.3565 . doi :10.1145/1806689.1806769.
• Chlebík, Miroslav; Chlebíková, Janka (2008). "El problema del árbol de Steiner en gráficos: resultados de inaproximabilidad". Informática Teórica . 406 (3): 207–214. doi : 10.1016/j.tcs.2008.06.046 .
• Chung, FRK ; Graham, RL (1985). "Un nuevo límite para los árboles mínimos euclidianos de Steiner". Geometría discreta y convexidad (Nueva York, 1982) . Anales de la Academia de Ciencias de Nueva York. vol. 440. Nueva York: Academia de Ciencias de Nueva York. págs. 328–346. Código bibliográfico : 1985NYASA.440..328C. doi :10.1111/j.1749-6632.1985.tb14564.x. SEÑOR  0809217.
• Cieslik, Dietmar (1998). Árboles mínimos de Steiner . Saltador. pag. 319.ISBN​ 0-7923-4983-0.
• Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek ; Woeginger, Gerhard (2000). "Árbol Steiner geométrico mínimo". Un compendio de problemas de optimización de NP .
• Cygan, Marek; Dell, Holger; Lokshtanov, Daniel; Marx, Daniel; Nederlof, Jesper; Okamoto, Yoshio; Paturi, Ramamohan; Saurabh, Saket; Wahlström, Magnus (2016). "Sobre problemas tan difíciles como CNF-SAT". Transacciones ACM sobre algoritmos . 12 (3): 41:1–41:24. arXiv : 1112.2275 . doi :10.1145/2925416. S2CID  7320634.
• Dom, Michael; Lokshtanov, Daniel; Saurabh, Saket (2014). "Límites inferiores de kernelización a través de colores e ID". Transacciones ACM sobre algoritmos . 11 (2): 13:1–13:20. doi :10.1145/2650261. S2CID  13570734.
• Dreyfus, SE; Wagner, RA (1971). "El problema de Steiner en gráficos". Redes . 1 (3): 195–207. doi :10.1002/net.3230010302.
• Fomin, Fedor V.; Kaski, Petteri; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket (2015). "Algoritmo espacial polinómico de tiempo exponencial único parametrizado para el árbol de Steiner". Autómatas, lenguajes y programación - 42º Coloquio Internacional, ICALP 2015, Actas, Parte I. págs. 494–505. doi :10.1007/978-3-662-47672-7_40. hdl : 1956/23311 .
• Fuchs, Benjamín; Kern, Walter; Molle, Daniel; Richter, Stefan; Rossmanith, Peter; Wang, Xinhui (2007). "Programación dinámica para árboles Steiner mínimos" (PDF) . Teoría de los Sistemas Computacionales . 41 (3): 493–500. doi :10.1007/s00224-007-1324-4. S2CID  7478978.
• Ganley, Joseph L. (2004). "Proporción Steiner". En negro, Paul E. (ed.). Diccionario de algoritmos y estructuras de datos. Instituto Nacional de Estándares y Tecnología de EE. UU . Consultado el 24 de mayo de 2012 .
• Garey, Michael R .; Johnson, David S. (1979). Computadoras e intratabilidad: una guía para la teoría de la integridad NP . Serie de libros de ciencias matemáticas (1ª ed.). Nueva York: WH Freeman and Company . ISBN 9780716710455. SEÑOR  0519066. OCLC  247570676., págs. 208-209, problemas ND12 y ND13.
• Hwang, FK (1976). "Sobre árboles mínimos de Steiner con distancia rectilínea". Revista SIAM de Matemática Aplicada . 30 (1): 104–114. doi :10.1137/0130013.
• Hwang, FK; Richards, DS; Invierno, P. (1992). El problema del árbol de Steiner . Anales de matemáticas discretas. vol. 53. Holanda Septentrional : Elsevier . ISBN 0-444-89098-X.
• Ivanov, Alejandro; Tuzhilin, Alexey (1994). Redes mínimas: el problema de Steiner y sus generalizaciones . NO, Boca Ratón, Florida: CRC Press . ISBN 978-0-8493-8642-8.
• Ivanov, Alejandro; Tuzhilin, Alexey (2000). Soluciones ramificadas a problemas variacionales unidimensionales . Singapur-Nueva Jersey-Londres-Hong Kong: World Scientific . ISBN 978-981-02-4060-8.
• Ivanov, Alejandro; Tuzhilin, Alexey (2003). Teoría de redes extremas (en ruso). Moscú-Izhevsk: Instituto de Investigaciones Informáticas. ISBN 5-93972-292-X.
• Ivanov, Alejandro; Tuzhilin, Alexey (2012). "La conjetura de Gilbert-Pollak del ratio Steiner todavía está abierta: declaración aclaratoria". Algorítmica . 62 (1–2): 630–632. doi :10.1007/s00453-011-9508-3. S2CID  7486839.
• Ivanov, Alejandro; Tuzhilin, Alexey (2015). "Revestimientos ramificados y relación Steiner". Transacciones Internacionales en Investigación Operativa . 23 (5): 875–882. arXiv : 1412.5433 . doi :10.1111/itor.12182. S2CID  3386263.
• Juhl, D.; Warmé, DM; Invierno, P.; Zachariasen, M. (enero de 2018). "El paquete de software GeoSteiner para calcular árboles de Steiner en el plano: un estudio computacional actualizado". Computación de programación matemática . 10 (4): 487–532. doi :10.1007/s12532-018-0135-8. S2CID  255616114.
• Rehfeldt, D.; Koch, T. (febrero de 2023). "Implicaciones, conflictos y reducciones para los árboles Steiner". Programación Matemática . 197 (2): 903–966. doi : 10.1007/s10107-021-01757-5 . S2CID  231842568.
• Karpinski, Marek; Zelikovsky, Alejandro (1998). "Aproximación de casos densos de problemas de cobertura". Actas del taller DIMACS sobre diseño de redes: conectividad y ubicación de instalaciones . Serie DIMACS en Matemática Discreta e Informática Teórica. vol. 40. Sociedad Matemática Estadounidense. págs. 169-178.
• Korte, Bernhard ; Vygen, Jens (2006). "Sección 20.1". Optimización combinatoria: teoría y algoritmos (3ª ed.). Saltador . ISBN 3-540-25684-9.
• Kou, L.; Markowsky, G.; Berman, L. (1 de junio de 1981). "Un algoritmo rápido para árboles Steiner". Acta Informática . 15 (2): 141-145. doi :10.1007/BF00288961. S2CID  21057232.
• Levin, A. Yu. (1971). "Algoritmo para la conexión más corta de un grupo de vértices de un gráfico". Doklady de matemáticas soviéticas . 12 : 1477-1481.
• Lokshtanov, Daniel; Nederlof, Jesper (2010). "Ahorro de espacio mediante algebraización". Actas del 42º Simposio ACM sobre Teoría de la Computación . págs. 321–330. doi :10.1145/1806689.1806735.
• Paolini, E.; Stepanov, E. (2012). «Resultados de existencia y regularidad del problema de Steiner» (PDF) . Calc. Var. Diferencia parcial. Ecuaciones . 46 (3–4): 837–860. doi :10.1007/s00526-012-0505-4. hdl : 2158/600141 . S2CID  55793499.
• Robins, Gabriel; Zelikovsky, Alejandro (2000). "Aproximación mejorada del árbol de Steiner en gráficos". Actas del undécimo simposio anual ACM-SIAM sobre algoritmos discretos (SODA '00). Filadelfia, PA, EE.UU.: Sociedad de Matemáticas Industriales y Aplicadas. págs. 770–779. ISBN 0-89871-453-2.
• Sherwani, Naveed A. (1993). Algoritmos para la automatización del diseño físico VLSI . Editores académicos de Kluwer. ISBN 9781475722192.
• Smith, JM; Invierno, P. (1995). "Geometría computacional y diseño de redes topológicas". En Du, Ding-Zhu; Hwang, Frank (eds.). Computación en geometría euclidiana . Serie de apuntes de conferencias sobre informática. vol. 4 (2ª ed.). River Edge, Nueva Jersey: World Scientific Publishing Co. págs. 351–451. ISBN 981-02-1876-1.
• Takahashi, Hiromitsu; Matsuyama, Akira (1980). "Una solución aproximada al problema de Steiner en gráficos". Matemáticas. Japónica . 24 (6): 573–577.
• Vazirani, Vijay V. (2003). Algoritmos de aproximación . Berlín: Springer. ISBN 3-540-65367-8.
• Wu, Bang Ye; Chao, Kun-Mao (2004). "Capítulo 7". Árboles de expansión y problemas de optimización . Chapman y Hall/CRC. ISBN 1-58488-436-3.
• Wu, YF; Widmayer, P.; Wong, CK (mayo de 1986). "Un algoritmo de aproximación más rápido para el problema de Steiner en gráficos". Acta Informática . 23 (2): 223–229. doi :10.1007/bf00289500. S2CID  7772232.

enlaces externos

• GeoSteiner (software para resolver problemas de árboles de Steiner euclidianos y rectilíneos; fuente disponible, gratuita para uso no comercial)
• SCIP-Jack (software para resolver el problema del árbol de Steiner en gráficos y 14 variantes, por ejemplo, el problema del árbol de Steiner para recoger premios; gratuito para uso no comercial)
• Subrutina de Fortran para encontrar el vértice de Steiner de un triángulo (es decir, el punto de Fermat ), sus distancias a los vértices del triángulo y los pesos relativos de los vértices.
• Phylomurka (Solucionador de problemas de árboles de Steiner a pequeña escala en gráficos)
• https://www.youtube.com/watch?v=PI6rAOWu-Og (Película: resolviendo el problema del árbol de Steiner con agua y jabón)
• Noormohammadpour, Mohammad; Raghavendra, Cauligi S.; Rao, Sriram; Kandula, Srikanth (2017), "Uso de árboles Steiner para minimizar los tiempos promedio de finalización de transferencias de datos masivas", DCCast: Transferencias eficientes de punto a multipunto en centros de datos, Asociación USENIX, arXiv : 1707.02096
• Hazewinkel, M. (2001) [1994], "Problema del árbol de Steiner", Enciclopedia de Matemáticas , EMS Press
• M. Hauptmann, M. Karpinski (2013): Un compendio sobre los problemas del árbol de Steiner