Я использую алгоритм Ленгауэра и Тарьяна со сжатием пути, чтобы вычислить дерево доминант для графа, где есть миллионы узлов. Алгоритм довольно сложный, и я должен признать, что я не нашел времени, чтобы полностью понять его, я просто использую его. Теперь мне нужно вычислить деревья-доминанты прямых потомков корневого узла и, возможно, откатить график вниз до определенной глубины, повторяя эту операцию. То есть когда я вычисляю дерево доминирующих для дочернего узла корневого узла, я хочу сделать вид, что корневой узел удален из графа.

Мой вопрос заключается в том, существует ли эффективное решение для этого, которое использует информацию о непосредственном доминирующем элементе, уже рассчитанную в исходном дереве доминирующих для корневого узла? Другими словами, я не хочу начинать с нуля для каждого из детей, потому что весь процесс довольно трудоемкий.

Наивно кажется, что это должно быть возможно, так как в глубине графа будет много узлов, у которых есть идомы чуть-чуть выше и на них не влияют изменения в верхней части графа.

Кстати, в стороне: странно, что тема деревьев-доминант "принадлежит" людям, занимающимся компиляцией, и об этом нет упоминания в книгах по классической теории графов. Приложение, для которого я его использую - мой Java-анализатор кучи FindRoots - не связано с теорией компилятора.

Уточнение: я говорю о ориентированных графах здесь. «Корень», на который я ссылаюсь, - это узел с наибольшей достижимостью. Я обновил текст выше, заменив ссылки на «дерево» на «график». Я склонен думать о них как о деревьях, потому что формав основном древовидная. График на самом деле состоит из объектов в куче Java и, как вы можете себе представить, является достаточно иерархическим. Я обнаружил, что дерево доминаторов полезно при анализе утечек OOM, потому что вас интересует «что поддерживает этот объект?» и ответ, в конечном счете, является его доминирующим. Деревья Dominator позволяют <ahem> видеть дерево, а не деревья. Но иногда много мусора всплывает на вершину дерева, так что у вас есть корень с тысячами детей прямо под ним. В таких случаях я хотел бы поэкспериментировать с вычислением деревьев-доминантных корней у каждого из прямых потомков (в исходном графике) корня, а затем, возможно, перейти на следующий уровень вниз и так далее. (Я стараюсь пока не беспокоиться о возможности обратных ссылок :)