Llave de árbol

Un árbol k -spanner (o simplemente k -spanner ) de un gráfico es un subárbol de expansión de en el que la distancia entre cada par de vértices es como máximo veces su distancia en . ${\displaystyle G}$ ${\displaystyle T}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle G}$

Resultados conocidos

Existen varios artículos escritos sobre el tema de los árboles de expansión. Uno de ellos se titulaba Tree Spanners ^[1] escrito por los matemáticos Leizhen Cai y Derek Corneil , que exploraba problemas teóricos y algorítmicos asociados con los árboles de expansión. Algunas de las conclusiones de ese artículo se enumeran a continuación. es siempre el número de vértices del grafo y es su número de aristas. ${\displaystyle n}$ ${\displaystyle m}$

1. Un árbol 1-spanner, si existe, es un árbol de expansión mínima y se puede encontrar en el tiempo (en términos de complejidad) para un grafo ponderado, donde . Además, cada árbol 1-spanner admisible en un grafo ponderado contiene un árbol de expansión mínima único. ${\displaystyle {\mathcal {O}}(m\log \beta (m,n))}$ ${\displaystyle \beta (m,n)=\min \left\{i\mid \log ^{i}n\leq m/n\right\}}$
2. Se puede construir un árbol 2-spanner en el tiempo, y el problema del árbol-spanner es NP-completo para cualquier entero fijo . ${\displaystyle {\mathcal {O}}(m+n)}$ ${\displaystyle t}$ ${\displaystyle t>3}$
3. La complejidad para encontrar un árbol extensor mínimo en un dígrafo es , donde es una inversa funcional de la función de Ackermann ${\displaystyle {\mathcal {O}}((m+n)\cdot \alpha (m+n,n))}$ ${\displaystyle \alpha (m+n,n)}$
4. El 1-spanner mínimo de un gráfico ponderado se puede encontrar en el tiempo. ${\displaystyle {\mathcal {O}}(mn+n^{2}\log(n))}$
5. Para cualquier número racional fijo , es NP-completo determinar si un gráfico ponderado contiene un árbol t-spanner, incluso si todos los pesos de los bordes son números enteros positivos. ${\displaystyle t>1}$
6. Se puede encontrar un árbol extensor (o un árbol extensor mínimo) de un dígrafo en tiempo lineal.
7. Un dígrafo contiene como máximo una llave de árbol.
8. El árbol cuasi-llave de un dígrafo ponderado se puede encontrar en el tiempo. ${\displaystyle {\mathcal {O}}(m\log \beta (m,n))}$

Véase también

• Llave de grafo
• Llave geométrica

Referencias

1. Cai, Leizhen; Corneil, Derek G. (1995). "Llaves de árboles". Revista SIAM de Matemáticas Discretas . 8 (3): 359–387. doi :10.1137/S0895480192237403.

• Handke, Dagmar; Kortsarz, Guy (2000), "Tree spanners for subgraphs and related tree coverage problems", Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000 Konstanz, Alemania, 15-17 de junio de 2000, Actas , Lecture Notes in Computer Science, vol. 1928, págs. 206-217, doi :10.1007/3-540-40064-8_20, ISBN 978-3-540-41183-3.