Árbol de expansión mínima cinética

Un árbol de expansión mínima cinético es una estructura de datos cinética que mantiene el árbol de expansión mínima (MST) de un grafo cuyos pesos de aristas cambian como una función continua del tiempo.

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

Agarwal et al. desarrollaron una estructura de datos que mantiene el MST para un grafo perteneciente a una familia cerrada menor . Utiliza la idea de un "intercambio", calculando la cantidad en la que aumentaría el peso del MST si alguna arista en el árbol e fuera reemplazada por una arista f fuera del árbol, de tal manera que el círculo inducido por f en el árbol contenga e . Mantener el árbol es entonces equivalente a encontrar e intercambiar el siguiente par para el cual esta cantidad se vuelve negativa. Esta estructura de datos considera la vista dual del grafo y luego divide en base a las particiones restringidas de Frederickson ^{[ 2 ]} para que esto sea eficiente. El resultado es un tiempo de ejecución total${\displaystyle O(pn^{\frac {1}{2}}\log ^{\frac {3}{2}}n)}$si${\displaystyle p}$se realizan inserciones o eliminaciones, o${\displaystyle O(n^{\frac {19}{12}}\log ^{\frac {3}{2}}n)}$Si solo se permiten cambios de peso. Estos límites deterministas mejoran ligeramente si se permite la aleatorización.

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