4551
правка
Полностью динамическая проверка на планарность: различия между версиями
Материал из WEGA
Полностью динамическая проверка на планарность (посмотреть исходный код)
Версия от 19:48, 26 июля 2014
, 26 июля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 9: | Строка 9: | ||
== Основные результаты == | == Основные результаты == | ||
Эппстайн и коллеги [3] предложили способ применения техники разрежения [ ] к семействам графов, уже являющихся разреженными – таким, как планарные графы. | Эппстайн и коллеги [3] предложили способ применения техники разрежения [2] к семействам графов, уже являющихся разреженными – таким, как планарные графы. | ||
Новые идеи, примененные в данном случае, заключаются в следующем. Понятие сертификата может быть расширено на определение графов, в которых подмножество вершин помечено как интересные; подобные сжатые сертификаты могут уменьшить размер графа за счет удаления неинтересных вершин. Используя это понятие, можно определить тип разрежения на основе разделителей – небольших множеств вершин, удаление которых разбивает граф на компоненты примерно равного размера. Рекурсивный поиск разделителей в этих компонентах дает в итоге дерево разделителей, которое может также использоваться как дерево разреженности; интересными вершинами для каждого сертификата будут вершины, использованные в разделителях на более высоких уровнях дерева. Вводится понятие сбалансированного дерева разделителей, которое также равномерно распределяет интересные вершины по дереву: такое дерево можно вычислить за линейное время и динамически поддерживать его. Используя эту технику, можно получить следующие результаты. | Новые идеи, примененные в данном случае, заключаются в следующем. Понятие сертификата может быть расширено на определение графов, в которых подмножество вершин помечено как интересные; подобные сжатые сертификаты могут уменьшить размер графа за счет удаления неинтересных вершин. Используя это понятие, можно определить тип разрежения на основе разделителей – небольших множеств вершин, удаление которых разбивает граф на компоненты примерно равного размера. Рекурсивный поиск разделителей в этих компонентах дает в итоге дерево разделителей, которое может также использоваться как дерево разреженности; интересными вершинами для каждого сертификата будут вершины, использованные в разделителях на более высоких уровнях дерева. Вводится понятие сбалансированного дерева разделителей, которое также равномерно распределяет интересные вершины по дереву: такое дерево можно вычислить за линейное время и динамически поддерживать его. Используя эту технику, можно получить следующие результаты. | ||
