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

Минимальные триангуляции были впервые описаны в середине семидесятых, и с тех пор было предложено множество алгоритмов. Полный обзор алгоритмов и различные характеризации хордальных графов и минимальных триангуляций можно найти в работе Хеггернеса и коллег [5], посвященной минимальным триангуляциям. Алгоритмы минимальных триангуляций можно грубо разделить на алгоритмы, получающие триангуляцию посредством упорядочивания удалений, и алгоритмы, получающие ее при помощи разделителей вершин. Большинство этих алгоритмов имеют время исполнения <math>O(nm) \; </math>, что для плотных графов превращается в <math>O(n^3) \; </math>. Среди алгоритмов, использующих упорядочивание удалений, самым быстрым на данный момент является алгоритм Кратча и Спинрада с временем исполнения <math>O(n^{2,69}) \; </math> [8]. Из алгоритмов, использующих разделители вершин, самым быстрым является алгоритм Хеггернеса и коллег [5] с временем исполнения <math>o(n^{2,376}) \; </math>, [5]. подробнее описанный ниже. И алгоритм Кратча и Спинрада [8], и алгоритм Хеггернеса и коллег используют алгоритм матричного умножения Копперсмита и Винограда [3], который позволяет получить алгоритм с временем исполнения <math>o(n^3) \; </math>.

Этот рекурсивный алгоритм определяет дерево, корнем которого является входной граф G, а каждая компонента связности <math>G[V \mathcal{n} A]</math> становится потомком корневой вершины, определяемой G. Этот процесс рекурсивно продолжается для каждой подзадачи, определяемой этими компонентами связности. Вершина H, являющаяся подзадачей алгоритма, находится на [[уровень|уровне]] i, если расстояние от H до корня дерева равно i. Заметим, что триангуляция всех подзадач одного и того же уровня может выполняться независимо. Пусть k – количество уровней. Если этот рекурсивный алгоритм может быть выполнен для каждого подграфа на каждом уровне за время <math>O(f(n)) \; </math>, тогда общее время исполнения составит <math>O(f(n) \cdot k) \; </math>.

Несмотря на то, что все подзадачи на одном и том же уровне могут решаться независимо, у них могут быть общие вершины и ребра, но не антиребра (т.е. пары вершин, не являющиеся смежными). Поскольку процесс триангуляции включает в себя добавление ребер, число антиребер на каждом уровне снижается, и сумма числа антиребер для всех подзадач на одном и том же уровне не может превышать <math>n^2 \; </math>. Алгоритм разбиения на рис. 2 использует этот факт; он имеет время исполнения <math>O(n^2 - m) \; </math>, что в сумме для каждого уровня дает <math>O(n^2) \; </math>. Таким образом, каждый уровень алгоритма быстрой минимальной триангуляции, приведенного на рис. 1, может быть выполнен за время <math>O(n^2 + n^{ \alpha }) \; </math>, где <math>O(n^{ \alpha }) \; </math> – время, необходимое для вычисления <math>MM^T \; </math>. Алгоритм разбиения на рис. 2 фактически находит множество A, которое определяет множество независимых разделителей, такое, что ни одна подзадача не содержит более четырех пятых всех антиребер исходного графа. В результате количество уровней алгоритма быстрой минимальной триангуляции не превышает <math>log_{ \frac{4}{5} }(n^2) = 2 \; log_{ \frac{4}{5} }(n)</math>, чем достигается время исполнения <math>O(n^{ \alpha } log \; n)</math>.

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

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