Тяжело-легкое разложение

В математике и теоретической информатике комбинаторной декомпозиция тяжелого-легкого пути (также называемая декомпозицией тяжелого пути ) — это метод разложения корневого дерева на набор путей . При декомпозиции тяжелого пути каждый нелистовой узел выбирает одно «тяжелое ребро», ребро дочернего элемента, которое имеет наибольшее количество потомков (произвольно разрывая связи). Выбранные ребра образуют пути разложения.

Разложение на пути

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

Альтернативно, пути тяжелых ребер могут быть расширены путем включения одного легкого ребра, от начала пути к его родителю. ^{[ 1 ]} В этом варианте разложения некоторые вершины принадлежат нескольким путям, но каждое ребро T принадлежит ровно одному пути.

Дерево путей

Пути декомпозиции сами по себе могут быть организованы в дерево, называемое «деревом путей», «деревом тяжелых путей» или «сжатым деревом». Каждый узел дерева путей соответствует пути декомпозиции тяжелого пути. Если p — путь декомпозиции тяжелого пути, то родительским элементом p в дереве путей является путь, содержащий родительский элемент головы p . Корнем дерева путей является путь, содержащий корень исходного дерева. Альтернативно, дерево путей может быть сформировано из исходного дерева путем сжатия всех тяжелых ребер.

«Легкое» ребро данного дерева — это ребро, которое не было выбрано в рамках декомпозиции тяжелого пути. Если легкое ребро соединяет два узла дерева x и y , причем x является родителем y , то у x должно быть как минимум в два раза больше потомков, чем у y . Следовательно, на любом пути от корня к листу дерева с n узлами может быть не более log ₂ n легких ребер. Эквивалентно, дерево путей имеет высоту не более log ₂ n .

Приложения

Декомпозиция тяжелых путей была введена Слиатором и Тарджаном (1983) как часть амортизированного анализа их древовидной структуры связей/вырезок . ^{[ 2 ]} и Harel & Tarjan (1984) как часть их структуры данных для самых низких общих предков , ^{[ 3 ]} Структура данных дерева связей/вырезок использует разделение динамического дерева на пути, которое не обязательно представляет собой декомпозицию тяжелого пути; в его анализе используется потенциальная функция, измеряющая расстояние от декомпозиции тяжелых путей, а небольшая высота дерева путей подразумевает, что каждая операция структуры данных выполняет лишь небольшое количество шагов, которые нельзя отнести к улучшениям этой функции. ^{[ 2 ]} В структуре данных с наименьшим общим предком разложение используется для встраивания входного дерева в полное двоичное дерево логарифмической глубины, что позволяет решать каждый запрос с помощью поразрядных операций с постоянным временем . ^{[ 3 ]}

Последующие применения декомпозиции тяжелых путей включали решение проблемы предка уровня . ^{[ 4 ]} вычисление расстояния редактирования между деревьями, ^{[ 5 ]}^{[ 6 ]} рисование графов и жадное встраивание , ^{[ 7 ]}^{[ 8 ]}^{[ 9 ]} нахождение пути возле всех узлов заданного графа, ^{[ 10 ]} диагностика неисправностей в волоконно-оптических сетях связи, ^{[ 1 ]} и декодирование кодов на основе грамматики , ^{[ 11 ]} среди других.

Ссылки

^ Перейти обратно: ^а ^б Харви, Николас Дж.А.; Патрашку, Михай ; Вэнь, Юнган; Еханин Сергей; Чан, Винсент В.С. (2007), «Неадаптивная диагностика неисправностей полностью оптических сетей посредством комбинаторного группового тестирования на графах», 26-я Международная конференция IEEE по компьютерным коммуникациям (INFOCOM 2007) , стр. 697–705, doi : 10.1109/INFCOM .2007.87
^ Перейти обратно: ^а ^б Слитор, Дэниел Д .; Тарьян, Роберт Эндре (1983), «Структура данных для динамических деревьев», Журнал компьютерных и системных наук , 26 (3): 362–391, doi : 10.1016/0022-0000(83)90006-5 , MR 0710253
^ Перейти обратно: ^а ^б Харель, Дов; Тарьян, Роберт Э. (1984), «Быстрые алгоритмы поиска ближайших общих предков», SIAM Journal on Computing , 13 (2): 338–355, doi : 10.1137/0213024
^ Дитц, Пол Ф. (1991), «Поиск предков уровней в динамических деревьях», Алгоритмы и структуры данных (Оттава, Онтарио, 1991) , Конспекты лекций по информатике, том. 519, Берлин: Springer, стр. 32–40, doi : 10.1007/BFb0028247 , MR 1146687.
^ Кляйн, Филип Н. (1998), «Вычисление расстояния редактирования между некорневыми упорядоченными деревьями», Алгоритмы - ESA '98 (Венеция) , Конспекты лекций по информатике, том. 1461, Берлин: Springer, стр. 91–102, doi : 10.1007/3-540-68530-8_8 , MR 1683332 , S2CID 9910968.
^ Демейн, Эрик Д .; Мозес, Шей; Россман, Бенджамин; Вейманн, Орен (2010), «Оптимальный алгоритм декомпозиции для расстояния редактирования дерева», Транзакции ACM по алгоритмам , 6 (1): A2, doi : 10.1007/978-3-540-73420-8_15 , MR 2654906
^ Бухсбаум, Адам Л.; Уэстбрук, Джеффри Р. (2000), «Поддержание иерархических представлений графов», Труды одиннадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (Сан-Франциско, Калифорния, 2000) , Нью-Йорк: ACM, стр. 566–575, MR 1755515
^ Эппштейн, Дэвид ; Гудрич, Майкл Т. (2011), «Краткая жадная геометрическая маршрутизация с использованием гиперболической геометрии», IEEE Transactions on Computers , 60 (11): 1571–1580, doi : 10.1109/TC.2010.257 , MR 2830035 , S2CID 40368995
^ Дункан, Кристиан А.; Эппштейн, Дэвид ; Гудрич, Майкл Т .; Кобуров, Стивен Г.; Нёлленбург, Мартин (2013), «Рисование деревьев с идеальным угловым разрешением и полиномиальной площадью», Дискретная и вычислительная геометрия , 49 (2): 157–182, arXiv : 1009.0581 , doi : 10.1007/s00454-012-9472-y , MR 3017904 , S2CID 254034095
^ Альструп, Стивен; Лауридсен, Питер В.; Зоммерлунд, Пер; Торуп, Миккель (1997), «Поиск ядер ограниченной длины», Алгоритмы и структуры данных , Конспект лекций по информатике, том 1272, Springer, стр. 45–54, doi : 10.1007/3-540-63307-3_47.
^ Билле, Филип; Ландау, Гад М.; Раман, Раджив; Садаканэ, Кунихико; Сатти, Шриниваса Рао; Вейманн, Орен (2011), «Произвольный доступ к строкам, сжатым грамматикой», Труды двадцать второго ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , Филадельфия, Пенсильвания: SIAM, стр. 373–389, MR 2857133

[hpwyk07-1] Перейти обратно: ^а ^б Харви, Николас Дж.А.; Патрашку, Михай ; Вэнь, Юнган; Еханин Сергей; Чан, Винсент В.С. (2007), «Неадаптивная диагностика неисправностей полностью оптических сетей посредством комбинаторного группового тестирования на графах», 26-я Международная конференция IEEE по компьютерным коммуникациям (INFOCOM 2007) , стр. 697–705, doi : 10.1109/INFCOM .2007.87

[st83-2] Перейти обратно: ^а ^б Слитор, Дэниел Д .; Тарьян, Роберт Эндре (1983), «Структура данных для динамических деревьев», Журнал компьютерных и системных наук , 26 (3): 362–391, doi : 10.1016/0022-0000(83)90006-5 , MR 0710253

[ht84-3] Перейти обратно: ^а ^б Харель, Дов; Тарьян, Роберт Э. (1984), «Быстрые алгоритмы поиска ближайших общих предков», SIAM Journal on Computing , 13 (2): 338–355, doi : 10.1137/0213024

[d91-4] Дитц, Пол Ф. (1991), «Поиск предков уровней в динамических деревьях», Алгоритмы и структуры данных (Оттава, Онтарио, 1991) , Конспекты лекций по информатике, том. 519, Берлин: Springer, стр. 32–40, doi : 10.1007/BFb0028247 , MR 1146687.

[k98-5] Кляйн, Филип Н. (1998), «Вычисление расстояния редактирования между некорневыми упорядоченными деревьями», Алгоритмы - ESA '98 (Венеция) , Конспекты лекций по информатике, том. 1461, Берлин: Springer, стр. 91–102, doi : 10.1007/3-540-68530-8_8 , MR 1683332 , S2CID 9910968.

[dmrw10-6] Демейн, Эрик Д .; Мозес, Шей; Россман, Бенджамин; Вейманн, Орен (2010), «Оптимальный алгоритм декомпозиции для расстояния редактирования дерева», Транзакции ACM по алгоритмам , 6 (1): A2, doi : 10.1007/978-3-540-73420-8_15 , MR 2654906

[bw00-7] Бухсбаум, Адам Л.; Уэстбрук, Джеффри Р. (2000), «Поддержание иерархических представлений графов», Труды одиннадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (Сан-Франциско, Калифорния, 2000) , Нью-Йорк: ACM, стр. 566–575, MR 1755515

[eg11-8] Эппштейн, Дэвид ; Гудрич, Майкл Т. (2011), «Краткая жадная геометрическая маршрутизация с использованием гиперболической геометрии», IEEE Transactions on Computers , 60 (11): 1571–1580, doi : 10.1109/TC.2010.257 , MR 2830035 , S2CID 40368995

[degkn13-9] Дункан, Кристиан А.; Эппштейн, Дэвид ; Гудрич, Майкл Т .; Кобуров, Стивен Г.; Нёлленбург, Мартин (2013), «Рисование деревьев с идеальным угловым разрешением и полиномиальной площадью», Дискретная и вычислительная геометрия , 49 (2): 157–182, arXiv : 1009.0581 , doi : 10.1007/s00454-012-9472-y , MR 3017904 , S2CID 254034095

[alst97-10] Альструп, Стивен; Лауридсен, Питер В.; Зоммерлунд, Пер; Торуп, Миккель (1997), «Поиск ядер ограниченной длины», Алгоритмы и структуры данных , Конспект лекций по информатике, том 1272, Springer, стр. 45–54, doi : 10.1007/3-540-63307-3_47.

[blrssw11-11] Билле, Филип; Ландау, Гад М.; Раман, Раджив; Садаканэ, Кунихико; Сатти, Шриниваса Рао; Вейманн, Орен (2011), «Произвольный доступ к строкам, сжатым грамматикой», Труды двадцать второго ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , Филадельфия, Пенсильвания: SIAM, стр. 373–389, MR 2857133

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]