Быстрая минимальная триангуляция: различия между версиями

== Ключевые слова и синонимы ==

[[Минимальная задача заполнения]]

== Постановка задачи ==

Быстрая минимальная триангуляция, рис. 1

Алгоритм быстрой минимальной триангуляции

== Основные результаты ==

Несмотря на то, что все подзадачи на одном и том же уровне могут решаться независимо, у них могут быть общие вершины и дуги, но не антидуги (т.е. пары вершин, не являющиеся смежными). Поскольку процесс триангуляции включает в себя добавление дуг, число антидуг на каждом уровне снижается, и сумма числа антидуг для всех подзадач на одном и том же уровне не может превышать n2. Алгоритм разбиения на рис. 2 использует этот факт; он имеет время исполнения O(n2 _ m), что в сумме для каждого уровня дает O(n2). Таким образом, каждый уровень алгоритма быстрой минимальной триангуляции, приведенного на рис. 1, может быть выполнен за время O(n2 + n˛), где O(n˛) – время, необходимое для вычисления MMT. Алгоритм разбиения на рис. 2 фактически находит множество A, которое определяет множество независимых разделителей, такое, что ни одна подзадача не содержит более четырех пятых всех антидуг исходного графа. В результате количество уровней алгоритма быстрой минимальной триангуляции не превышает log4/5(n2) = 2log4/5(n), чем достигается время исполнения O(n˛ log n).

== Применение ==

Возможно, из-за связи с первоначальной задачей первые алгоритмы минимальной триангуляции были основаны на упорядочении и давали в результате порядок, называемый минимальным порядком удаления. С тех пор задача нахождения минимальной триангуляции получила широкое распространение; были опубликованы несколько новых вариантов применения и характеризаций, касающихся свойств разделителей вершин. В числе таких новых вариантов применения – нахождение древесной ширины графа и реконструкция эволюционной истории при помощи филогенетических деревьев [6]. Новые характеризации минимальной триангуляции на основе разделителей вершин повысили уровень знаний о минимальных триангуляциях [1,7,9]. Одним из результатов, основанных на этих характеризациях, является алгоритм вычисления древесной ширины графа за полиномиальное время в случае, когда количество минимальных разделителей полиномиально ограничено [2]. Другим вариантом применения являются более быстрые точные алгоритмы вычисления древесной ширины графа с полиномиальным временем исполнения [4].

== Открытые вопросы ==

Приведенный алгоритм позволяет найти минимальную триангуляцию за время O((n2 + и") log n), где O(n˛) – время, необходимое для проведения бинарного матричного умножения n х n. В результате любое улучшение алгоритма бинарного матричного умножения позволит повысить скорость алгоритма нахождения минимальной триангуляции. Интересный вопрос заключается в том, верно ли обратное: существует ли алгоритм бинарного матричного умножения с временем O((n2 + n^)f(n)), где O(n˛) – время, необходимое для нахождения минимальной триангуляции и f(n) = о{па~2) или по меньшей мере f(n) = O(n). Более простой и релевантный вопрос был ранее задан в [8]: сложнее ли вычислить минимальную триангуляцию, чем определить, содержит ли граф хотя бы один треугольник? Более алгоритмический вопрос выглядит следующим образом: существует ли алгоритм нахождения минимальной триангуляции за время O(n2 + na).

== См. также ==

* ''[[Древесная ширина графов]]

== Литература ==