Árbol de expansión mínimo cinético

Un árbol de expansión mínimo cinético es una estructura de datos cinéticos que mantiene el árbol de expansión mínimo (MST) de un gráfico cuyos pesos de borde cambian como una función continua del tiempo.

La estructura de datos conocida más eficiente para el caso general utiliza una lista clasificada cinética para almacenar los pesos de los bordes y un algoritmo MST estándar para calcular el MST dados los pesos de los bordes ordenados. Esta estructura de datos debe procesar eventos, el desarrollo de una estructura de datos más eficiente sigue siendo un problema abierto. ^[1] ${\ Displaystyle O (n ^ {2})}$

Agarwal y col. desarrolló una estructura de datos que mantiene el MST para un gráfico perteneciente a una familia cerrada menor . Utiliza la idea de un "intercambio", calculando la cantidad por la cual el peso del MST aumentaría si algún borde en el árbol $e$ fuera reemplazado por un borde $f$ fuera del árbol de manera que el círculo inducido por $f$ en el árbol contenga $e$ . Mantener el árbol equivale entonces a encontrar e intercambiar el siguiente par para el que esta cantidad se vuelve negativa. Esta estructura de datos considera la vista dual del gráfico y luego se divide según las particiones restringidas de Frederickson ^[2]para hacer esto eficiente. Da como resultado un tiempo de ejecución total si se realizan inserciones o eliminaciones, o si solo se permiten cambios de peso. Estos límites deterministas mejoran ligeramente si se permite la aleatorización. ${\ Displaystyle O (pn ^ {\ frac {1} {2}} \ log ^ {\ frac {3} {2}} n)}$ ${\ Displaystyle p}$ ${\ Displaystyle O (n ^ {\ frac {19} {12}} \ log ^ {\ frac {3} {2}} n)}$

Agarwal, Pankaj; Eppstein, David; Guibas, Leonidas J .; Henzinger, Monika R. (1998). Árboles de expansión mínima paramétrica y cinética (PDF) . FOCS . Consultado el 19 de mayo de 2012 .