Estoy usando el algoritmo de Lengauer y Tarjan con compresión de ruta para calcular el árbol dominador para un gráfico donde hay millones de nodos. El algoritmo es bastante complejo y debo admitir que no me he tomado el tiempo para entenderlo completamente, solo lo estoy usando. Ahora tengo la necesidad de calcular los árboles dominadores de los hijos directos del nodo raíz y, posiblemente, repetir el gráfico hasta una cierta profundidad repitiendo esta operación. Es decir. Cuando calculo el árbol dominador para un hijo del nodo raíz, quiero fingir que el nodo raíz se ha eliminado del gráfico.

Mi pregunta es si existe una solución eficiente para esto que haga uso de la información de dominador inmediata ya calculada en el árbol de dominador inicial para el nodo raíz. En otras palabras, no quiero comenzar desde cero para cada uno de los niños porque todo el proceso lleva bastante tiempo.

Ingenuamente parece que debe ser posible ya que habrá muchos nodos en el fondo del gráfico que tienen idoms un poco más arriba y no se ven afectados por los cambios en la parte superior del gráfico.

Por cierto, aparte de eso: es extraño que el tema de los árboles dominadores sea "propiedad" de los compiladores y no se menciona en los libros de teoría clásica de gráficos. La aplicación para la que lo estoy usando, mi analizador de montón de Java FindRoots, no está relacionada con la teoría del compilador.

Aclaración: estoy hablando de gráficos dirigidos aquí. La "raíz" a la que me refiero es en realidad el nodo con mayor accesibilidad. He actualizado el texto anterior reemplazando las referencias a "árbol" con "gráfico". Tiendo a pensar en ellos como árboles porque la forma esprincipalmente como un árbol El gráfico es en realidad de los objetos en un montón de Java y, como puede imaginar, es razonablemente jerárquico. He encontrado que el árbol dominador es útil al hacer un análisis de fugas OOM porque lo que le interesa es "¿qué mantiene vivo este objeto?" y la respuesta en última instancia es su dominador. Los árboles dominadores le permiten <ahem> ver la madera en lugar de los árboles. Pero a veces, mucha basura flota hasta la parte superior del árbol, por lo que tiene una raíz con miles de niños directamente debajo. Para tales casos, me gustaría experimentar con el cálculo de los árboles dominadores enraizados en cada uno de los hijos directos (en el gráfico original) de la raíz y luego tal vez pasar al siguiente nivel hacia abajo y así sucesivamente. (Estoy tratando de no preocuparme por la posibilidad de enlaces de retroceso por el momento :)