Problema del árbol de Steiner

Sobre redes de conexión cortas con vértices añadidos

Árbol de Steiner para tres puntos A , B y C (nótese que no hay conexiones directas entre A , B y C ). El punto de Steiner S se encuentra en el punto de Fermat del triángulo ABC .

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

En matemáticas combinatorias , el problema del árbol de Steiner , o problema del árbol mínimo de Steiner , llamado así por 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 dado de objetos y una función objetivo predefinida . Una variante bien conocida, que a menudo se usa como sinónimo del término problema del árbol de Steiner, es el problema del árbol de Steiner en grafos . Dado un grafo no dirigido con pesos de arista no negativos y un subconjunto de vértices, generalmente denominados terminales, el problema del árbol de Steiner en grafos 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 aristas. Otras variantes bien conocidas son el problema del árbol de Steiner euclidiano y el problema del árbol de Steiner mínimo rectilíneo .

El problema del árbol de Steiner en grafos 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 grafos contiene exactamente dos terminales, se reduce a encontrar el camino más corto. Si, por otro lado, todos los vértices son terminales, el problema del árbol de Steiner en grafos es equivalente al árbol de expansión mínima. Sin embargo, mientras que tanto el problema del camino más corto no negativo como el del árbol de expansión mínima son solucionables 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 dada tiene un árbol de peso menor que un umbral dado, es NP-completo , lo que implica que la variante de optimización, que pregunta por el árbol de peso mínimo en un grafo dado, es NP-duro . De hecho, la variante de decisión estaba entre los 21 problemas NP-completos originales de Karp . El problema del árbol de Steiner en grafos tiene aplicaciones en el diseño de circuitos o redes . Sin embargo, las aplicaciones prácticas generalmente requieren variaciones, lo que da lugar a una multitud de variantes del problema del árbol de Steiner.

La mayoría de las versiones del problema del árbol de Steiner son NP-hard, pero algunos casos restringidos se pueden resolver en tiempo polinomial. A pesar de la complejidad pesimista del peor caso , varias variantes del problema del árbol de Steiner, incluido el problema del árbol de Steiner en grafos 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 de Steiner euclidiano

Árboles de 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 de Steiner.

El problema original se planteó en la forma que se ha conocido como el problema del árbol de Steiner euclidiano o el problema del árbol de Steiner geométrico : dados N puntos en el plano , el objetivo es conectarlos mediante líneas de longitud total mínima de tal manera que dos puntos cualesquiera puedan interconectarse mediante segmentos de línea, ya sea directamente o a través de otros puntos y segmentos de línea.

Aunque el problema debe su nombre a Steiner, fue planteado por primera vez en 1811 por Joseph Diez Gergonne de la siguiente forma: "Varias ciudades están situadas en posiciones conocidas sobre un plano; el problema consiste en unirlas 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 de conexión no se intersecan entre sí excepto en los puntos finales y forman un árbol, de ahí el nombre del problema.

El problema de N  = 3 ha sido considerado durante mucho tiempo, y rápidamente se extendió al problema de encontrar una red en estrella con un solo eje que conecte a todos los N puntos dados, de longitud total mínima. Sin embargo, aunque el problema del árbol de Steiner completo 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 de Steiner euclidiano, los puntos añadidos al grafo ( puntos de Steiner ) deben tener un grado de tres, y las tres aristas incidentes a dicho punto deben formar tres ángulos de 120 grados (véase punto de Fermat ). De ello se deduce que el número máximo de puntos de Steiner que puede tener un árbol de 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 a 120 grados, la solución viene dada por un punto de Steiner situado en el punto de Fermat ; en caso contrario la solución viene dada por los dos lados del triángulo que se encuentran en el ángulo de 120 o más grados.

Para N general , el problema del árbol de Steiner euclidiano es NP-duro 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 de tiempo polinomial (PTAS) para árboles de Steiner euclidianos, es decir, se puede encontrar una solución casi óptima en tiempo polinomial. ^[5] No se sabe si el problema del árbol de Steiner euclidiano es NP-completo, ya que no se conoce la pertenencia a la clase de complejidad NP.

Árbol de 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 sustituye 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 los cables se lleva a cabo mediante cables que a menudo están restringidos por las reglas de diseño para correr solo en direcciones verticales y horizontales, por lo que el problema del árbol de Steiner rectilíneo 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 han sido ampliamente estudiados en el contexto de grafos ponderados . El prototipo es, posiblemente, el problema del árbol de Steiner en grafos . Sea G  = ( V ,  E ) un grafo no dirigido con pesos de arista no negativos c y sea S  ⊆  V un subconjunto de vértices, llamados terminales . Un árbol de Steiner es un árbol en G que abarca S. Hay dos versiones del problema: en el problema de optimización asociado con los árboles de Steiner, la tarea es encontrar un árbol de 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 lo tanto, el problema de optimización es NP-duro . Los problemas de árboles de Steiner en grafos se aplican a varios 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 grafo 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 otro modo, los pesos de las aristas satisfacen la desigualdad triangular . Esta variante se conoce como el problema del árbol de Steiner métrico . 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 del árbol de Steiner métrico es APX-completo , es decir, a menos que P = NP , es imposible lograr razones 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, la aproximación 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 1.25. ^[13] Karpinski y Alexander Zelikovsky construyeron PTAS para las instancias densas de problemas de árboles de Steiner. ^[14] ${\displaystyle \ln(4)+\varepsilon \approx 1.386}$ ${\displaystyle 96/95\approx 1.0105}$

En un caso especial del problema de grafos, el problema del árbol de Steiner para grafos 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 de Steiner con k aristas conectadas y el problema de la red de Steiner con k vértices conectados , donde el objetivo es encontrar un grafo con k aristas conectadas o un grafo con k vértices conectados en lugar de cualquier grafo conexo. Otra generalización bien estudiada ^[16] es el problema de diseño de red superviviente (SNDP), donde la tarea es conectar cada par de vértices con un número dado (posiblemente 0) de caminos disjuntos en aristas o vértices.

El problema de Steiner también se ha planteado en el contexto general de los espacios métricos y posiblemente para un número infinito de puntos. ^[17]

Aproximación del árbol de Steiner

El problema general del árbol de Steiner del grafo puede aproximarse calculando el árbol de expansión mínimo del subgrafo del cierre métrico del grafo inducido por los vértices terminales, como lo publicaron por primera vez en 1981 Kou et al. ^[18] El cierre métrico de un grafo G es el grafo completo en el que cada arista está ponderada por la distancia de ruta más corta entre los nodos en G . Este algoritmo produce un árbol cuyo peso está dentro de un factor 2 − 2/ t del peso del árbol de Steiner óptimo donde t es el número de hojas en el árbol de Steiner óptimo; esto puede demostrarse considerando un recorrido de un vendedor ambulante en el árbol de Steiner óptimo. Esta solución aproximada se puede calcular en tiempo polinomial O(|S| |V|²) resolviendo primero el problema de las rutas más cortas de todos los pares para calcular el cierre métrico, luego resolviendo el problema del árbol de expansión mínimo .

Otro algoritmo popular para aproximar el árbol de Steiner en grafos fue publicado por Takahashi y Matsuyama en 1980. ^[19] Su solución construye de manera incremental el árbol de Steiner comenzando desde un vértice arbitrario y agregando repetidamente la ruta más corta desde el árbol hasta el vértice más cercano en S que aún no se haya agregado. Este algoritmo también tiene un tiempo de ejecución de O(| S | | V |²) y produce un árbol cuyo peso está dentro de 2 − 2/| S | del óptimo.

En 1986, Wu et al. ^[20] mejoraron drásticamente el tiempo de ejecución al evitar el cálculo previo de las rutas más cortas de todos los pares. En su lugar, adoptan un enfoque similar al algoritmo de Kruskal para calcular un árbol de expansión mínimo, comenzando desde un bosque de | S | árboles disjuntos y "haciéndolos 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 queda un árbol. Al utilizar un Heap (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 mejora la relación de costo 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 razones de aproximación que mejoraron la razón 2 − 2/ t . Esta secuencia culminó con el algoritmo de Robins y Zelikovsky en 2000, que mejoró la razón a 1,55 mediante la mejora iterativa del árbol de expansión terminal de costo mínimo. Sin embargo, más recientemente, Byrka et al. demostraron 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 general del árbol de Steiner del grafo es tratable 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 n es el número de vértices del grafo y S 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 W es el peso máximo de cualquier arista. ^{[23] [24]} Una desventaja de los algoritmos mencionados anteriormente es que utilizan el espacio exponencial ; existen algoritmos de espacio polinomial que se ejecutan en el tiempo y en el tiempo. ^{[25] [26]} ${\displaystyle 3^{|S|}{\text{poly}}(n)}$ ${\displaystyle c^{|S|}{\text{poly}}(n)}$ ${\displaystyle c>2}$ ${\displaystyle 2^{|S|}{\text{poly}}(n)W}$ ${\displaystyle 2^{|S|}{\text{poly}}(n)W}$ ${\displaystyle (7.97)^{|S|}{\text{poly}}(n)\log W}$

Se sabe que el problema general del árbol de Steiner del grafo no tiene un algoritmo parametrizado que se ejecute en el tiempo para cualquier , donde t es el número de aristas del árbol de Steiner óptimo, a menos que el problema de cobertura de conjuntos tenga un algoritmo que se ejecute en el tiempo para algún , donde n y m 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 polinomial a menos que , incluso parametrizado por el número de aristas del árbol de Steiner óptimo y si todos los pesos de las aristas son 1. ^[28] ${\displaystyle 2^{\epsilon t}{\text{poly}}(n)}$ ${\displaystyle \epsilon <1}$ ${\displaystyle 2^{\epsilon n}{\text{poly}}(m)}$ ${\displaystyle \epsilon <1}$ ${\displaystyle {\textsf {coNP}}\subseteq {\textsf {NP/poly}}}$

Aproximación parametrizada del árbol de Steiner

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

Al parametrizar el problema del árbol de Steiner del grafo por el número p de no terminales (vértices de Steiner) en la solución óptima, el problema es W[1]-duro (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 \varepsilon >0}$ ${\displaystyle (1+\varepsilon )}$ ${\displaystyle 2^{O(p^{2}/\varepsilon ^{4})}n^{O(1)}}$

Relación de Steiner

El coeficiente de Steiner es el supremo del cociente 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 de Steiner euclidiano, se conjetura que el cociente de Steiner es , el cociente que se logra con tres puntos en un triángulo equilátero con un árbol de expansión que utiliza dos lados del triángulo y un árbol de Steiner que conecta los puntos a través del centroide del triángulo. A pesar de afirmaciones anteriores de una prueba, ^[32] la conjetura aún está abierta. ^{[33] El mejor} límite superior ampliamente aceptado para el problema es 1.2134, de Chung & 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 con cuatro puntos en un cuadrado con un árbol de expansión que utiliza 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 los ejes. ${\displaystyle {\tfrac {3}{2}}}$ ${\displaystyle L_{1}}$ ${\displaystyle 45^{\circ }}$ ${\displaystyle L_{\infty }}$

Véase también

• Problema del bosque opaco
• Problema del viajante de comercio

Notas

1. Rehfeldt y Koch (2023).
2. Juhl y otros (2018).
3. Marcus Brazil, Ronald L. Graham, Doreen A. Thomas y Martin Zachariasen, "Sobre la historia del problema del árbol de Steiner euclidiano", 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 otros (2000).
6. Sherwani (1993), pág. 228.
7. Ljubić, Ivana (2021). "Resolución de á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, Roman; Rugelj, Joz̆e; Kandus, Gorazd (1 de octubre de 2001). "Una nota sobre enrutamiento multicast distribuido en redes punto a punto". Computers & Operations Research . 28 (12): 1149–1164. doi :10.1016/S0305-0548(00)00029-0. ISSN  0305-0548.
9. Klimm, Florian; Toledo, Enrique M.; Monfeuga, Thomas; Zhang, Fang; 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 de células individuales con redes de interacción proteína-proteína". BMC Genomics . 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 supervivientes: 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 otros (2007).
24. Björklund y otros (2007).
25. Lokshtanov y Nederlof (2010).
26. Fomin y otros (2015).
27. Cygan y otros (2016).
28. Dom, Lokshtanov y Saurabh (2014).
29. Lokshtanov, Daniel; Panolan, Fahad; Ramanujan, MS; Saurabh, Saket (19 de junio de 2017). "Nerpelización con pérdida". Actas del 49.° Simposio anual ACM SIGACT sobre teoría de la computación (PDF) . STOC 2017. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 224–237. doi :10.1145/3055399.3055456. ISBN . 978-1-4503-4528-6. Número de identificación del sujeto  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. El New York Times del 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, Alexander (2009). "Algoritmo de aproximación 1.25 para el problema del árbol de Steiner con distancias 1 y 2". Algorithms and Data Structures: 11th International Symposium, WADS 2009, Banff, Canadá, 21-23 de agosto de 2009, Actas . Lecture Notes in Computer Science. Vol. 5664. págs. 86-97. arXiv : 0810.1851 . doi :10.1007/978-3-642-03367-4_8. ISBN . 978-3-642-03366-7.
• Bern, Marshall W.; Graham, Ronald L. (1989). "El problema de la red más corta". Scientific American . 260 (1): 84–89. Código Bibliográfico :1989SciAm.260a..84B. doi :10.1038/scientificamerican0189-84.
• Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko (2007). "Fourier Meets Möbius: Fast Subset Convolution". Actas del 39.° Simposio ACM sobre teoría de la computación . págs. 67–74. arXiv : cs/0611101 . doi :10.1145/1250790.1250801. ISBN . 978-1-59593-631-8.
• 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. ISBN . 978-1-4503-0050-6.
• 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 de Steiner euclidianos". 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. MR  0809217.
• Cieslik, Dietmar (1998). Árboles mínimos de Steiner . Springer. pág. 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 mediante colores e identificadores". ACM Transactions on Algorithms . 11 (2): 13:1–13:20. doi :10.1145/2650261. S2CID  13570734.
• Dreyfus, SE; Wagner, RA (1971). "El problema de Steiner en grafos". Redes . 1 (3): 195–207. doi :10.1002/net.3230010302.
• Fomin, Fedor V.; Kaski, Petteri; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket (2015). "Algoritmo de espacio polinomial temporal exponencial único parametrizado para árbol de Steiner". Autómatas, lenguajes y programación – 42.º coloquio internacional, ICALP 2015, actas, parte I. Apuntes de clase en informática. Vol. 9134. págs. 494–505. doi :10.1007/978-3-662-47672-7_40. hdl : 1956/23311 . ISBN . 978-3-662-47671-0.
• 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). "Steiner ratio". En Black, Paul E. (ed.). Dictionary of Algorithms and Data Structures. Instituto Nacional de Estándares y Tecnología de Estados Unidos . 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 NP-completitud . Serie de libros sobre ciencias matemáticas (1.ª ed.). Nueva York: WH Freeman and Company . ISBN 9780716710455. Sr.  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áticas Aplicadas . 30 (1): 104–114. doi :10.1137/0130013.
• Hwang, FK; Richards, DS; Winter, P. (1992). El problema del árbol de Steiner . Anales de matemáticas discretas. Vol. 53. Holanda septentrional : Elsevier . ISBN. 0-444-89098-X.
• Ivanov, Alexander; Tuzhilin, Alexey (1994). Redes mínimas: el problema de Steiner y sus generalizaciones . NW, Boca Raton, Florida: CRC Press . ISBN. 978-0-8493-8642-8.
• Ivanov, Alexander; Tuzhilin, Alexey (2000). Soluciones ramificadas para problemas variacionales unidimensionales . Singapur-Nueva Jersey-Londres-Hong Kong: World Scientific . ISBN 978-981-02-4060-8.
• Ivanov, Alexander; Tuzhilin, Alexey (2003). Teoría de redes extremas (en ruso). Moscú-Izhevsk: Instituto de Investigaciones Informáticas. ISBN 5-93972-292-X.
• Ivanov, Alexander; Tuzhilin, Alexey (2012). "La conjetura de Gilbert–Pollak sobre la relación de Steiner aún está abierta: declaración aclaratoria". Algorithmica . 62 (1–2): 630–632. doi :10.1007/s00453-011-9508-3. S2CID  7486839.
• Ivanov, Alexander; Tuzhilin, Alexey (2015). "Recubrimientos ramificados y ratio de Steiner". Transacciones internacionales en investigación operativa . 23 (5): 875–882. ​​arXiv : 1412.5433 . doi :10.1111/itor.12182. S2CID  3386263.
• Juhl, D.; Warme, DM; Winter, 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 árboles de Steiner". Programación matemática . 197 (2): 903–966. doi : 10.1007/s10107-021-01757-5 . S2CID  231842568.
• Karpinski, Marek; Zelikovsky, Alexander (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áticas discretas y ciencias de la computación teórica. Vol. 40. Sociedad Matemática Americana. págs. 169–178.
• Korte, Bernhard ; Vygen, Jens (2006). "Sección 20.1". Optimización combinatoria: teoría y algoritmos (3.ª ed.). Springer . 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 grafos". Matemáticas soviéticas Doklady . 12 : 1477–1481.
• Lokshtanov, Daniel; Nederlof, Jesper (2010). "Ahorro de espacio mediante algebrización". Actas del 42.º Simposio ACM sobre teoría de la computación . págs. 321–330. doi :10.1145/1806689.1806735. ISBN . 978-1-4503-0050-6.
• Paolini, E.; Stepanov, E. (2012). "Resultados de existencia y regularidad para el problema de Steiner" (PDF) . Calc. Var. Ecuaciones de diferencias parciales . 46 (3–4): 837–860. doi :10.1007/s00526-012-0505-4. hdl : 2158/600141 . S2CID  55793499.
• Robins, Gabriel; Zelikovsky, Alexander (2000). "Aproximación mejorada del árbol de Steiner en grafos". Actas del undécimo simposio anual ACM-SIAM sobre algoritmos discretos (SODA '00). Filadelfia, Pensilvania, EE. UU.: Society for Industrial and Applied Mathematics. págs. 770–779. ISBN 0-89871-453-2.
• Sherwani, Naveed A. (1993). Algoritmos para la automatización del diseño físico VLSI . Kluwer Academic Publishers. ISBN 9781475722192.
• Smith, JM; Winter, 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 notas de clase sobre computación. Vol. 4 (2.ª ed.). River Edge, NJ: World Scientific Publishing Co. págs. 351–451. ISBN 981-02-1876-1.
• Takahashi, Hiromitsu; Matsuyama, Akira (1980). "Una solución aproximada para el problema de Steiner en grafos". Math. Japonica . 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 & 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 grafos". Acta Informatica . 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; código fuente disponible, gratuito 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 con recolección de 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 desde 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: solucionando el problema del árbol de Steiner con agua y jabón)
• Noormohammadpour, Mohammad; Raghavendra, Cauligi S.; Rao, Sriram; Kandula, Srikanth (2017), "Uso de árboles de Steiner para minimizar los tiempos de finalización promedio de transferencias de datos en masa", DCCast: transferencias eficientes de punto a multipunto entre centros de datos, USENIX Association, 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 problemas de árboles de Steiner