Maneira eficiente de calcular recursivamente a árvore dominadora?
Estou usando o algoritmo Lengauer e Tarjan com compactação de caminho para calcular a árvore dominadora para um gráfico em que existem milhões de nós. O algoritmo é bastante complexo e tenho que admitir que não tomei tempo para entendê-lo completamente, estou apenas usando-o. Agora, preciso calcular as árvores dominadoras dos filhos diretos do nó raiz e, possivelmente, recuar no gráfico até uma certa profundidade, repetindo esta operação. I.e. Quando calculo a árvore dominadora para um filho do nó raiz, quero fingir que o nó raiz foi removido do gráfico.
Minha pergunta é se existe uma solução eficiente para isso que utilize as informações imediatas do dominador já calculadas na árvore inicial do dominador para o nó raiz? Em outras palavras, não quero começar do zero para cada uma das crianças, porque todo o processo é bastante demorado.
Ingenuamente, parece que deve ser possível, pois haverá muitos nós no fundo do gráfico que possuem códigos um pouco acima deles e não são afetados pelas alterações na parte superior do gráfico.
Aliás, do mesmo modo: é bizarro que o assunto das árvores dominadoras seja "de propriedade" das pessoas do compilador e não há menção disso nos livros sobre a teoria clássica dos grafos. O aplicativo para o qual estou usando - meu analisador de pilha Java FindRoots - não está relacionado à teoria do compilador.
Esclarecimento: Estou falando de gráficos direcionados aqui. A "raiz" a que me refiro é, na verdade, o nó com maior alcance. Atualizei o texto acima, substituindo as referências a "árvore" por "gráfico". Eu costumo pensar nelas como árvores porque a forma éprincipalmente como uma árvore. Na verdade, o gráfico é dos objetos em uma pilha de java e, como você pode imaginar, é razoavelmente hierárquico. Eu achei a árvore dominadora útil ao fazer a análise de vazamento do OOM porque o que você está interessado é em "o que mantém esse objeto vivo?" e a resposta, em última análise, é seu dominador. As árvores dominadoras permitem que você <ahem> veja a madeira em vez das árvores. Às vezes, porém, muitas porcarias flutuam para o topo da árvore, para que você tenha uma raiz com milhares de filhos diretamente abaixo dela. Para tais casos, eu gostaria de experimentar o cálculo das árvores dominadoras enraizadas em cada um dos filhos diretos (no gráfico original) da raiz e, em seguida, talvez ir para o próximo nível abaixo e assim por diante. (Estou tentando não me preocupar com a possibilidade de voltar links por enquanto :)